language: Haskell (ghc-7.4.1) date: 753 days 4 hours ago link: visibility: public private user's deleted
```<!--/**
* GeSHi (C) 2004 - 2007 Nigel McNie, 2007 - 2008 Benny Baumann
* (http://qbnz.com/highlighter/ and http://geshi.org/)
*/
.haskell .imp {font-weight: bold; color: red;}
.haskell .kw1 {color: #06c; font-weight: bold;}
.haskell .kw2 {color: #06c; font-weight: bold;}
.haskell .kw4 {color: #cccc00; font-weight: bold;}
.haskell .co1 {color: #5d478b; font-style: italic;}
.haskell .co2 {color: #339933; font-weight: bold;}
.haskell .co3 {color: #5d478b; font-style: italic;}
.haskell .coMULTI {color: #5d478b; font-style: italic;}
.haskell .es0 {background-color: #3cb371; font-weight: bold;}
.haskell .sy0 {color: #339933; font-weight: bold;}
.ln, .ln{ vertical-align: top; }
-->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 )
`1000000`
`15485863`