Log in

No account? Create an account
March 3rd, 2007 - Adventures in Engineering — LiveJournal
The wanderings of a modern ronin.

Ben Cantrick
  Date: 2007-03-03 02:14
  Subject:   More primality tests in Haskell.
  Mood:der uber-nerd
  Tags:  haskell, programming

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

Read more...Collapse )
8 Comments | Post A Comment | | Link

May 2015