fork(3) download
  1. {-# OPTIONS_GHC -O2 #-} -- unbounded merging idea due to Richard Bird
  2. module Main where -- double staged production idea due to Melissa O'Neill
  3. -- tree folding idea Dave Bayer / Heinrich Apfelmus
  4. main = -- simplified formulation Will Ness
  5. do s <- getLine
  6. print $ take 5 $ drop (read s-5) primes -- logBase (n2/n1) (t2/t1): ~ n^1.20
  7.  
  8. primes :: [Int]
  9. primes = 2 : _Y ((3 :) . gaps 5 . unionAll . map (\x-> [x*x, x*x+2*x..]))
  10.  
  11. _Y g = g (_Y g) -- telescoping feed (recursive)
  12. -- = g xs where xs = g xs -- double feed (corecursive)
  13.  
  14. gaps k s@(x:xs) | k < x = k : gaps (k+2) s -- == [k,k+2..]\\s , when
  15. | otherwise = gaps (k+2) xs -- k<=x && null(s\\[k,k+2..])
  16.  
  17. unionAll ((x:xs):t) = x : (union xs . unionAll . pairs) t
  18. where
  19. pairs (xs:ys:t) = union xs ys : pairs t
  20. union a@(x:xs) b@(y:ys) = case compare x y of
  21. LT -> x : union xs b
  22. EQ -> x : union xs ys
  23. GT -> y : union a ys
Success #stdin #stdout 7.32s 7364KB
stdin
2000000
stdout
[32452781,32452789,32452837,32452841,32452843]