{-# OPTIONS_GHC -O2 #-}
module Main where
import Array
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
-}
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKaW1wb3J0IEFycmF5Cm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzICgpICEhIChyZWFkIHMgLSAxKSkKIApwcmltZXMgOjogKCkgLT4gW0ludF0KcHJpbWVzICgpID0gMjogcHJpbWVzJyAgIC0tIG1hcmtpbmcgb2ZmIGNvbXBvc2l0ZXMgb24gQXJyYXkgc2VnbWVudHMKIHdoZXJlICAgICAgICAgICAgICAgICAgIC0tIGJldHdlZW4gY29uc2VjdXRpdmUgcHJpbWVzIHNxdWFyZXMsIG9uIG9kZHMKICAgcHJpbWVzJyA9IDM6IHNpZXZlIHByaW1lcycgMyBbXQogICBzaWV2ZSAocDpwcykgeCBmcyA9IAogICAgIGxldCAKICAgICAgICAgcSA9IChwKnAteClgZGl2YDIgICAgICAgICAgICAgICAgICAKICAgICAgICAgYSA9IGFjY3VtQXJyYXkgKFxiIGMtPiBGYWxzZSkgVHJ1ZSAKICAgICAgICAgICAgICAgICAoMSxxLTEpCiAgICAgICAgICAgICAgICAgWyhpLCgpKSB8IChzLHkpIDwtIGZzLCBpIDwtIFt5K3MseStzK3MuLnFdXQogICAgIGluICAKICAgICAgICBbaSoyICsgeCB8IChpLGUpIDwtIGFzc29jcyBhLCBlXQogICAgICAgICsrIHNpZXZlIHBzIChwKnApCiAgICAgICAgICAgICAgICAgKChwLDApOlsocyxyZW0gKHktcSkgcykgfCAocyx5KSA8LSBmc10pCgp7LQpzZWdtZW50ZWQgZ2VuZXJhdGlvbjogICAgICAgICAgICAgTyhuXikgICAgICAgICAgZGVsdGEgIE8obl4pCiAgICAgMSwwMDA6ICAgICAgIDcsOTE5ICAgIDAuMDBzICAgICAgICAgIDMuN01CICAgICAgCiAgICAzMCwwMDA6ICAgICAzNTAsMzc3ICAgIDAuMDlzICAgICAgICAgIDQuN01CICAgMS4wICAgCiAgIDEwMCwwMDA6ICAgMSwyOTksNzA5ICAgIDAuNTFzICAxLjQ0ICAgIDUuOE1CICAgMi4xICAgMC42CiAgIDMwMCwwMDA6ICAgNCwyNTYsMjMzICAgIDIuNDlzICAxLjQ0ICAgMTIuOU1CICAgOS4yICAgMS4zICAwLjkKICAgNjAwLDAwMDogICA4LDk2MCw0NTMgICAgNi43N3MgIDEuNDQgICAyMS4xTUIgIDE3LjQgICAwLjkgIDEuMiAgMS4wCiAxLDAwMCwwMDA6ICAxNSw0ODUsODYzICAgMTQuMDlzICAxLjQzICAgMzguNU1CICAzNC44ICAgMS40ICAwLjkgIDEuMiAgMS4wCiAKQVJSL29kZHM6ICAgICAgICAgICAgICAgICAgICAgICAgIE8obl4pICAgICAgICAgIGRlbHRhICBPKG5eKQogICAgIDEsMDAwOiAgICAgICAgICAgICAgICAwLjAwcyAgICAgICAgICAzLjdNQiAKICAgIDMwLDAwMDogICAgICAgICAgICAgICAgMC4wMnMgICAgICAgICAgNC44TUIgICAxLjEKICAgMTAwLDAwMDogICAgICAgICAgICAgICAgMC4wNnMgICAgICAgICAgNy44TUIgICA0LjEgICAxLjEKICAgMzAwLDAwMDogICAgICAgICAgICAgICAgMC4yN3MgICAgICAgICAxNy4xTUIgIDEzLjQgICAxLjEKICAgNjAwLDAwMDogICAgICAgICAgICAgICAgMC42MXMgIDEuMTggICAzMC4zTUIgIDI2LjYgICAxLjAKICAgIDEgIG1sbjogIDE1LDQ4NSw4NjMgICAgMS4xOHMgIDEuMjkgICA1Mi45TUIgIDQ5LjIgICAxLjIgCiAgICAyICBtbG46ICAzMiw0NTIsODQzICAgIDIuODRzICAxLjI3ICAgODcuN01CICA4NC4wICAgMC44IAogICAgMyAgbWxuOiAgNDksOTc5LDY4NyAgICA1LjAxcyAgMS40MCAgMTM3LjlNQiAxMzQuMiAgIDEuMiAgMC45CiAgICA0ICBtbG46ICA2Nyw4NjcsOTY3ICAgIDguNDRzICAxLjgxICAyMDMuNE1CIDE5OS43ICAgMS40ICAxLjIgIAogICAgNSAgbWxuOiAgODYsMDI4LDEyMSAgIDExLjkwcyAgMS41NCAgMjQwLjNNQiAyMzYuNiAgIDAuOCAgMS4xICAxLjEKLX0=