language: Haskell (ghc-7.4.1)
date: 753 days 4 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

{-# OPTIONS_GHC -O2 #-}
module Main where
import Array
main = interact (\s-> show $ primes () !! (read s - 1))
 
primes :: () -> [Int]
primes () = 2: primes'   -- marking off composites on Array segments
 where                   -- between consecutive primes squares, on odds
   primes' = 3: sieve primes' 3 []
   sieve (p:ps) x fs = 
     let 
         q = (p*p-x)`div`2                  
         a = accumArray (\b c-> False) True 
                 (1,q-1)
                 [(i,()) | (s,y) <- fs, i <- [y+s,y+s+s..q]]
     in  
        [i*2 + x | (i,e) <- assocs a, e]
        ++ sieve ps (p*p)
                 ((p,0):[(s,rem (y-q) s) | (s,y) <- fs])
 
{-
segmented generation:             O(n^)          delta  O(n^)
     1,000:       7,919    0.00s          3.7MB      
    30,000:     350,377    0.09s          4.7MB   1.0   
   100,000:   1,299,709    0.51s  1.44    5.8MB   2.1   0.6
   300,000:   4,256,233    2.49s  1.44   12.9MB   9.2   1.3  0.9
   600,000:   8,960,453    6.77s  1.44   21.1MB  17.4   0.9  1.2  1.0
 1,000,000:  15,485,863   14.09s  1.43   38.5MB  34.8   1.4  0.9  1.2  1.0
 
ARR/odds:                         O(n^)          delta  O(n^)
     1,000:                0.00s          3.7MB 
    30,000:                0.02s          4.8MB   1.1
   100,000:                0.06s          7.8MB   4.1   1.1
   300,000:                0.27s         17.1MB  13.4   1.1
   600,000:                0.61s  1.18   30.3MB  26.6   1.0
    1  mln:  15,485,863    1.18s  1.29   52.9MB  49.2   1.2 
    2  mln:  32,452,843    2.84s  1.27   87.7MB  84.0   0.8 
    3  mln:  49,979,687    5.01s  1.40  137.9MB 134.2   1.2  0.9
    4  mln:  67,867,967    8.44s  1.81  203.4MB 199.7   1.4  1.2  
    5  mln:  86,028,121   11.90s  1.54  240.3MB 236.6   0.8  1.1  1.1
-}
[1 of 1] Compiling Main             ( prog.hs, prog.o )
Linking prog ...