
After my last adventure in prime testing, I decided that I should implement the Sieve of Erastosthenes and give that a whirl. There's full code at the Haskell pastebin if you're morbidly curious. But most of it is the NewtonRapheson approximate square root routines. The entire Sieve of Erastosthenes function is only 5 lines long:
listPrimes :: Integer > [Integer] > Integer > [Integer] listPrimes n knownPrimes m  m > n = knownPrimes  not (any (== 0) (map (m `mod`) knownPrimes)) = listPrimes n (m:knownPrimes) (m+2)  otherwise = listPrimes n knownPrimes (m+2)
This generates all primes less than the number n, starting at the number m, and using the initial list of primes given in the "knownPrimes" list. m is assumed to be odd and greater than 2, and only odd numbers less than n are checked for primality. The full list of generated primes is returned.
For example, listPrimes 100 [2] 3 gives [97,89,83,79,73,71,67,61,59,53,47,43,41,3
( Read more...Collapse )