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 Newton-Rapheson 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  3 gives [97,89,83,79,73,71,67,61,59,53,47,43,41,3
( Collapse )