March 3rd, 2007


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,37,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 )