fork download
  1. {-# OPTIONS_GHC -O2 #-}
  2. main = print $ primes !! 1000000
  3.  
  4. primes :: [Int]
  5. primes = 2 : _Y( (3:) . sieve 5 . unionAll . map (\p->[p*p, p*p+2*p..]) )
  6. where
  7. _Y g = g (_Y g) -- non-sharing fixpoint combinator
  8.  
  9. unionAll ((x:xs):t) = x : (union xs . unionAll . pairs) t
  10. pairs (xs:ys:t) = union xs ys : pairs t
  11. sieve k s@(x:xs) | k<x = k : sieve (k+2) s -- equivalent to
  12. | True = sieve (k+2) xs -- [k,k+2..]`minus`s, k<=x
  13.  
  14. union (x:xs) (y:ys) = case compare x y of
  15. LT -> x : union xs (y:ys)
  16. EQ -> x : union xs ys
  17. GT -> y : union (x:xs) ys
Success #stdin #stdout 3.02s 6752KB
stdin
100k:  0.25s  6.8 MB
200k:  0.57s  6.8 MB    n^1.19      -- timings for odds::[Integer], no -O2
400k:  1.31s  6.7 MB    n^1.20
800k:  3.05s  6.7 MB    n^1.22
1mln:  4.01s  6.7 MB    n^1.22
1.5m:  6.53s  6.7 MB    n^1.20
stdout
15485867