{-# OPTIONS_GHC -O2 #-}
module Main where
primes () = 2: primes' -- LINEAR-folding multiples-union
where -- ERATOSthenes sieve
primes' = 3: sieve primes' 3 []
sieve (p:ps) x fs =
let
q=p*p
in
([x+2,x+4..q-2] `minus`
foldl union [] [[y+s,y+2*s..q] | (s,y) <- fs])
++ sieve ps q
((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])
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
{-
FOLDL FOLDR
50,000: 611,953 0.15s 5.8MB 0.44s 5.8MB
100,000: 1,299,709 0.41s 7.8MB 1.28s 8.8MB
200,000: 2,750,159 1.09s 14.0MB 3.83s 14.0MB
300,000: 4,256,233 1.93s 19.1MB 7.08s 19.1MB
400,000: 5,800,079 2.95s 25.2MB 11.08s 24.2MB
500,000: 7,368,787 3.94s 28.2MB > 15 sec >30.4MB
1,000,000: 15,485,863 10.93s 58.0MB > 15 sec >30.4MB
O(n^1.45) O(n^0.9)
-}
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzKCkgISEgKHJlYWQgcyAtIDEpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBMSU5FQVItZm9sZGluZyBtdWx0aXBsZXMtdW5pb24gCiB3aGVyZSAgICAgICAgICAgICAgICAgICAtLSAgRVJBVE9TdGhlbmVzIHNpZXZlCiAgIHByaW1lcycgID0gMzogc2lldmUgcHJpbWVzJyAzIFtdCiAgIHNpZXZlIChwOnBzKSB4IGZzID0gCiAgICAgbGV0IAogICAgICAgICBxPXAqcCAKICAgICBpbgogICAgICAgIChbeCsyLHgrNC4ucS0yXSBgbWludXNgIAogICAgICAgICAgICBmb2xkbCB1bmlvbiBbXSBbW3krcyx5KzIqcy4ucV0gfCAocyx5KSA8LSBmc10pCiAgICAgICAgKysgc2lldmUgcHMgcSAKICAgICAgICAgICAgICAgKCgyKnAscSk6WyhzLHEtcmVtIChxLXkpIHMpIHwgKHMseSkgPC0gZnNdKQoKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFUSAtPiB4IDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiBhICB5cwogICB1bmlvbiBhICAgICAgICBbXSAgICAgICA9IGEKICAgdW5pb24gW10gICAgICAgYiAgICAgICAgPSBiCiAKICAgbWludXMgYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IG1pbnVzIHhzIGIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEVRIC0+ICAgICBtaW51cyB4cyB5cwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgR1QgLT4gICAgIG1pbnVzIGEgIHlzCiAgIG1pbnVzIGEgICAgICAgIGIgICAgICAgID0gYQoKey0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIEZPTERMICAgICAgICAgICAgIEZPTERSIAogICAgNTAsMDAwOiAgICA2MTEsOTUzICAgMC4xNXMgIDUuOE1CICAgICAgMC40NHMgICA1LjhNQgogICAxMDAsMDAwOiAgMSwyOTksNzA5ICAgMC40MXMgIDcuOE1CICAgICAgMS4yOHMgICA4LjhNQgogICAyMDAsMDAwOiAgMiw3NTAsMTU5ICAgMS4wOXMgMTQuME1CICAgICAgMy44M3MgIDE0LjBNQgogICAzMDAsMDAwOiAgNCwyNTYsMjMzICAgMS45M3MgMTkuMU1CICAgICAgNy4wOHMgIDE5LjFNQgogICA0MDAsMDAwOiAgNSw4MDAsMDc5ICAgMi45NXMgMjUuMk1CICAgICAxMS4wOHMgIDI0LjJNQiAKICAgNTAwLDAwMDogIDcsMzY4LDc4NyAgIDMuOTRzIDI4LjJNQiAgID4gMTUgc2VjID4zMC40TUIKIDEsMDAwLDAwMDogMTUsNDg1LDg2MyAgMTAuOTNzIDU4LjBNQiAgID4gMTUgc2VjID4zMC40TUIKCiAgICAgICAgICAgICAgICAgICAgIE8obl4xLjQ1KSBPKG5eMC45KQotfQ==