fork(1) download
  1. {-# OPTIONS_GHC -O2 #-}
  2. module Main where
  3.  
  4. main = interact (\s-> show $ primes() !! (read s - 1))
  5.  
  6. primes :: () -> [Int]
  7. primes () = 2: primes' -- TREE-folding multiples-union
  8. where -- ERATOSthenes sieve
  9. primes' = 3: sieve primes' 5 9 []
  10. sieve (p:ps) x q fs =
  11. ([x,x+2..q-2] `minus`
  12. foldt [[y+s,y+2*s..q] | (s,y) <- fs])
  13. ++ sieve ps (q+2) (head ps^2)
  14. ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
  15.  
  16. foldt (a:xs) = union a (foldt (pairs xs))
  17. foldt [] = []
  18. pairs (a:b:xs) = union a b : pairs xs
  19. pairs xs = xs
  20.  
  21. union [email protected](x:xs) [email protected](y:ys) = case compare x y of
  22. LT -> x : union xs b
  23. EQ -> x : union xs ys
  24. GT -> y : union a ys
  25. union a [] = a
  26. union [] b = b
  27.  
  28. minus [email protected](x:xs) [email protected](y:ys) = case compare x y of
  29. LT -> x : minus xs b
  30. EQ -> minus xs ys
  31. GT -> minus a ys
  32. minus a b = a
  33.  
  34. {- FOLDT (w/ foldr) (w/ foldl)
  35. 100,000: 1,299,709 0.23s 6.8MB 0.40s 7.8MB 1.33s 8.8MB
  36. 0.5 mln: 7,368,787 1.54s 25.2MB 3.80s 31.3MB 300k:7.35s 19MB
  37. 1.0 mln: 15,485,863 3.65s 48.8MB 10.31s 57.0MB 450k:14.1s 28MB
  38. 2.0 mln: 32,452,843 8.74s 110.2MB
  39. 2.5 mln: 41,161,739 12.02s 134.8MB
  40.  
  41. O(n^1.28) O(n^1.1) (n^1.41) (n^1.3) (n^1.57) (^2.1)
  42. -}
stdin
1000000
compilation info
[1 of 1] Compiling Main             ( prog.hs, prog.o )
Linking prog ...
stdout
15485863