{-# OPTIONS_GHC -O2 #-}
module Main where
primes () = 2: primes' -- Segmented Generation w/ rem filtering
where
primes' = 3: sieve primes' 3 0
sieve (p:ps) x k =
let
q = p*p
fs = take k primes'
in
[n
| n
<-[x
+2,x
+4..q
-2], and [rem n f
/=0 | f
<-fs
]] ++ sieve ps q (k+1)
{-
postponed filters: O(n^) delta O(n^)
1,000: 7,919 0.00s 3.7MB 0.0
30,000: 350,377 0.16s 5.8MB 2.1
100,000: 1,299,709 0.92s 1.45 9.9MB 6.2 0.90
300,000: 4,256,233 4.60s 1.46 21.1MB 17.4 0.94
600,000: 8,960,453 13.27s 1.50 38.5MB 34.8 1.00
segmented generation/filtering: O(n^) delta O(n^)
1,000: 7,919 0.00s 3.7MB 0.0
30,000: 350,377 0.09s 4.7MB 1.0
100,000: 1,299,709 0.51s 1.44 5.8MB 2.1 0.62
300,000: 4,256,233 2.49s 1.44 12.9MB 9.2 1.34 0.92
600,000: 8,960,453 6.77s 1.44 21.1MB 17.4 0.92 1.20 0.95
1,000,000: 15,485,863 14.09s 1.43 38.5MB 34.8 1.36 0.91 1.20 1.0
-}
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93IChwcmltZXMoKSAhISAocmVhZCBzIC0gMSkpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBTZWdtZW50ZWQgR2VuZXJhdGlvbiB3LyByZW0gZmlsdGVyaW5nCiB3aGVyZQogICBwcmltZXMnID0gMzogc2lldmUgcHJpbWVzJyAzIDAKICAgc2lldmUgKHA6cHMpIHggayA9CiAgICAgbGV0CiAgICAgICAgIHEgID0gcCpwCiAgICAgICAgIGZzID0gdGFrZSBrIHByaW1lcycKICAgICBpbgogICAgICAgIFtuIHwgbjwtW3grMix4KzQuLnEtMl0sIGFuZCBbcmVtIG4gZi89MCB8IGY8LWZzXV0KICAgICAgICArKyBzaWV2ZSBwcyBxIChrKzEpCgp7LQpwb3N0cG9uZWQgZmlsdGVyczogICAgICAgICAgICAgICAgTyhuXikgICAgICAgICAgZGVsdGEgIE8obl4pCiAgICAgMSwwMDA6ICAgICAgIDcsOTE5ICAgIDAuMDBzICAgICAgICAgIDMuN01CICAgMC4wCiAgICAzMCwwMDA6ICAgICAzNTAsMzc3ICAgIDAuMTZzICAgICAgICAgIDUuOE1CICAgMi4xCiAgIDEwMCwwMDA6ICAgMSwyOTksNzA5ICAgIDAuOTJzICAxLjQ1ICAgIDkuOU1CICAgNi4yICAgMC45MAogICAzMDAsMDAwOiAgIDQsMjU2LDIzMyAgICA0LjYwcyAgMS40NiAgIDIxLjFNQiAgMTcuNCAgIDAuOTQKICAgNjAwLDAwMDogICA4LDk2MCw0NTMgICAxMy4yN3MgIDEuNTAgICAzOC41TUIgIDM0LjggICAxLjAwCiAKc2VnbWVudGVkIGdlbmVyYXRpb24vZmlsdGVyaW5nOiAgIE8obl4pICAgICAgICAgIGRlbHRhICBPKG5eKQogICAgIDEsMDAwOiAgICAgICA3LDkxOSAgICAwLjAwcyAgICAgICAgICAzLjdNQiAgIDAuMCAgIAogICAgMzAsMDAwOiAgICAgMzUwLDM3NyAgICAwLjA5cyAgICAgICAgICA0LjdNQiAgIDEuMCAgIAogICAxMDAsMDAwOiAgIDEsMjk5LDcwOSAgICAwLjUxcyAgMS40NCAgICA1LjhNQiAgIDIuMSAgIDAuNjIKICAgMzAwLDAwMDogICA0LDI1NiwyMzMgICAgMi40OXMgIDEuNDQgICAxMi45TUIgICA5LjIgICAxLjM0ICAwLjkyCiAgIDYwMCwwMDA6ICAgOCw5NjAsNDUzICAgIDYuNzdzICAxLjQ0ICAgMjEuMU1CICAxNy40ICAgMC45MiAgMS4yMCAgMC45NQogMSwwMDAsMDAwOiAgMTUsNDg1LDg2MyAgIDE0LjA5cyAgMS40MyAgIDM4LjVNQiAgMzQuOCAgIDEuMzYgIDAuOTEgIDEuMjAgIDEuMAotfQ==