### More primality tests in Haskell.

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 [2] 3`gives

`[97,89,83,79,73,71,67,61,59,53,47,43,41,3`7,31,29,23,19,17,13,11,7,5,3,2] . (1 is not on the list, because we're assuming that you already know that every number is evenly divisible by one.)

**( Collapse )**