Difference between revisions of "Prime numbers"
Jump to navigation
Jump to search
(Realized more readable code was as fast with -O") |
(Much faster sieve implementation) |
||
Line 21: | Line 21: | ||
(Note the use of <hask>takeWhile</hask> to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!) |
(Note the use of <hask>takeWhile</hask> to prevent the infinite list of primes requiring an infinite amount of CPU time and RAM to process!) |
||
− | The following is a more efficient |
+ | The following is a more efficient prime generator, implementing the sieve of |
+ | Eratosthenes: |
||
<haskell> |
<haskell> |
||
+ | merge xs@(x:xt) ys@(y:yt) = case compare x y of |
||
− | primes :: [Int] |
||
− | + | LT -> x : (merge xt ys) |
|
− | + | EQ -> x : (merge xt yt) |
|
+ | GT -> y : (merge xs yt) |
||
− | g n p = p <= (floor $ sqrt ((fromIntegral n) :: Double)) |
||
+ | |||
− | h n = all (f n) $ takeWhile (g n) primes |
||
+ | diff xs@(x:xt) ys@(y:yt) = case compare x y of |
||
+ | LT -> x : (diff xt ys) |
||
+ | EQ -> diff xt yt |
||
+ | GT -> diff xs yt |
||
+ | |||
+ | merge' (x:xt) ys = x : (merge xt ys) |
||
+ | |||
+ | primes = ps ++ (diff ns $ foldr1 merge' $ map f $ tail primes) |
||
+ | where ps = [2,3,5] |
||
+ | ns = [7,9..] |
||
+ | f p = [ m*p | m <- [p,p+2..]] |
||
</haskell> |
</haskell> |
||
+ | <hask>merge'</hask> effectively implements a heap, exploiting Haskell's lazy evaluation model. For another example of this idiom see the Prelude's <hask>ShowS</hask> type, which again exploits Haskell's lazy evaluation model |
||
− | Be sure to compile with optimization on, so the partial application <hask>(g n)</hask> isn't recomputed for each use. |
||
+ | to avoid explicitly coding efficient concatenable strings. |
||
[[Category:Code]] |
[[Category:Code]] |
Revision as of 21:19, 9 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 prime generator, implementing the sieve of Eratosthenes:
merge xs@(x:xt) ys@(y:yt) = case compare x y of
LT -> x : (merge xt ys)
EQ -> x : (merge xt yt)
GT -> y : (merge xs yt)
diff xs@(x:xt) ys@(y:yt) = case compare x y of
LT -> x : (diff xt ys)
EQ -> diff xt yt
GT -> diff xs yt
merge' (x:xt) ys = x : (merge xt ys)
primes = ps ++ (diff ns $ foldr1 merge' $ map f $ tail primes)
where ps = [2,3,5]
ns = [7,9..]
f p = [ m*p | m <- [p,p+2..]]
merge'
effectively implements a heap, exploiting Haskell's lazy evaluation model. For another example of this idiom see the Prelude's ShowS
type, which again exploits Haskell's lazy evaluation model
to avoid explicitly coding efficient concatenable strings.