Difference between revisions of "Prime numbers"
Jump to navigation
Jump to search
(Added efficient version of prime sieve) |
(Realized more readable code was as fast with -O") |
||
Line 27: | Line 27: | ||
primes = 2 : (filter h [3,5..]) where |
primes = 2 : (filter h [3,5..]) where |
||
f n p = rem n p /= 0 |
f n p = rem n p /= 0 |
||
− | g n = floor $ sqrt ((fromIntegral n) :: Double) |
+ | g n p = p <= (floor $ sqrt ((fromIntegral n) :: Double)) |
− | h n = all (f n) $ takeWhile |
+ | h n = all (f n) $ takeWhile (g n) primes |
</haskell> |
</haskell> |
||
+ | Be sure to compile with optimization on, so the partial application <hask>(g n)</hask> isn't recomputed for each use. |
||
[[Category:Code]] |
[[Category:Code]] |
Revision as of 08:16, 5 July 2007
The following is an elegant (and highly inefficient) way to generate a list of all the prime numbers in the universe:
primes = sieve [2..] where
sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)
With this definition made, a few other useful (??) functions can be added:
is_prime n = n `elem` (takeWhile (n >=) primes)
factors n = filter (\p -> n `mod` p == 0) primes
factorise 1 = []
factorise n =
let f = head $ factors n
in f : factorise (n `div` f)
(Note the use of takeWhile
to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!)
The following is a more efficient version of the same sieve:
primes :: [Int]
primes = 2 : (filter h [3,5..]) where
f n p = rem n p /= 0
g n p = p <= (floor $ sqrt ((fromIntegral n) :: Double))
h n = all (f n) $ takeWhile (g n) primes
Be sure to compile with optimization on, so the partial application (g n)
isn't recomputed for each use.