First stab at primality-test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import Analytics.Theory.Number         -- http://lpaste.net/107480

-- solution to 1HaskellADay exercise at http://lpaste.net/107463

-- isPrime :: Integer -> Bool is defined in the imported library, so:

mbprimes :: [Integer]
mbprimes = [2, 3, 7, 11, 12, 13, 17, 19, 29, 31, 127, 2047, 8192, 
            131071, 131091, 524287, 536870911]

answers :: [Bool]
answers = map isPrime mbprimes

{--

*Main> answers 
[True,True,True,True,False,True,True,True,True,True,True,False,False,
 True,False,True,False]

returned in almost no time, but

*Analytics.Theory.Number Data.Time.Clock> getCurrentTime >>= \st -> 
            return (isPrime 2147483647) >>= \ans -> 
            getCurrentTime >>= \et -> return (ans, diffUTCTime et st)
(...[time passes]... True,0.000004s) -- that took much longer than indicated

is taking no small amount of time, even though

*Analytics.Theory.Number> sqrt (1.0 * 2147483647) -- optimal check upper-bound
46340.950001051984

Now, an even more efficient implementation is not to use factors at all,
or to use the prime factors, so stepping proceeds much more quickly.

Or we could do something else entirely, but that's a discussion for later,
perhaps.

 --}