**Paste:**#107483**Author(s):**1HaskellADay**Language:**Haskell**Channel:**-**Created:**2014-07-14 17:55:34 UTC**Revisions:**- 2014-07-14 18:58:48 UTC #107486 (diff): No title (1HaskellADay)
- 2014-07-14 17:56:09 UTC #107484 (diff): No title (1HaskellADay)
- 2014-07-14 17:55:34 UTC #107483: First stab at primality-test (1HaskellADay)

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. --} |