language: Haskell (ghc-7.4.1)
date: 555 days 2 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

{-# OPTIONS_GHC -O2 #-}
module Main where
 
main = interact (\s-> show $ primes() !! (read s - 1))
 
primes :: () -> [Int]
primes () = 2: primes'   -- TREE-folding multiples-union
 where                   --  ERATOSthenes sieve
   primes'  = 3: sieve primes' 5 9 []
   sieve (p:ps) x q fs = 
        ([x,x+2..q-2] `minus` 
                          foldt [[y+s,y+2*s..q] | (s,y) <- fs])
        ++ sieve ps (q+2) (head ps^2)
             ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
    
   foldt (a:xs)     = union a (foldt (pairs xs)) 
   foldt []         = []
   pairs (a:b:xs)   = union a b : pairs xs
   pairs xs         = xs
   
   union a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : union xs b 
                                  EQ -> x : union xs ys
                                  GT -> y : union a  ys
   union a        []       = a
   union []       b        = b
   
   minus a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : minus xs b
                                  EQ ->     minus xs ys
                                  GT ->     minus a  ys
   minus a        b        = a
   
{-                           FOLDT            (w/ foldr)        (w/ foldl)
   100,000:  1,299,709   0.23s    6.8MB      0.40s   7.8MB      1.33s  8.8MB
   0.5 mln:  7,368,787   1.54s   25.2MB      3.80s  31.3MB    300k:7.35s 19MB
   1.0 mln: 15,485,863   3.65s   48.8MB     10.31s  57.0MB    450k:14.1s 28MB
   2.0 mln: 32,452,843   8.74s  110.2MB  
   2.5 mln: 41,161,739  12.02s  134.8MB
   
                     O(n^1.28)  O(n^1.1)   (n^1.41) (n^1.3)   (n^1.57) (^2.1)
-}
[1 of 1] Compiling Main             ( prog.hs, prog.o )
Linking prog ...
TREE-folding segmented ERATOSthenes sieve :: [Int] -- primes generated without composites, found as union of all the preceding primes\' multiples on each segment between the primes squares -- O(n^1.28) time, O(n^0.9) space, -- 100,000-th: 0.23s-6.8MB 1,000,000-th: 3.73s-57.0MB