fork(4) download
  1. {-# OPTIONS_GHC -O2 -fno-cse #-}
  2. primesTMWE = 2:3:5:7: gapsW 11 wheel (joinT3 $ hitsW 11 wheel primes')
  3. where
  4. primes' = 11: gapsW 13 (tail wheel) (joinT3 $ hitsW 11 wheel primes')
  5.  
  6. gapsW k ws@(d:w) cs@(c:u) | k==c = gapsW (k+d) w u
  7. | otherwise = k : gapsW (k+d) w cs
  8. hitsW k ws@(d:w) ps@(p:u) | k==p = scanl (\c d->c+p*d) (p*p) ws
  9. : hitsW (k+d) w u
  10. | otherwise = hitsW (k+d) w ps
  11. joinT3 ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)
  12. `union` joinT3 (pairs t)
  13. wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
  14. 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
  15.  
  16. main = do
  17. x <- read `fmap` getLine -- 100k 1mln 2mln 4mln
  18. mapM_ print -- 6.8MB 6.8MB 6.8MB 6.8MB -- !!!!!
  19. . take 2 . map fst -- 0.13s 2.09s 4.87s 11.25s
  20. . tail . iterate (splitAt 10.snd) -- n^1.21 n^1.22 n^1.21 -- !!!!
  21. $ ([], drop (x-10) primesTMWE)
  22.  
  23. pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t
  24. union (x:xs) (y:ys) = case (compare x y) of
  25. LT -> x : union xs (y:ys)
  26. EQ -> x : union xs ys
  27. GT -> y : union (x:xs) ys
Success #stdin #stdout 11.25s 6784KB
stdin
4000000
stdout
[67867831,67867843,67867901,67867903,67867907,67867937,67867949,67867951,67867957,67867967]
[67867979,67867999,67868011,67868023,67868041,67868069,67868077,67868111,67868123,67868153]