{-# OPTIONS_GHC -O2 #-}
module Main where
primes () = 2: primes' -- TREE-folding multiples-union
where -- ERATOSthenes sieve
primes' = 3: sieve primes' 5 9 []
sieve (p:ps) x q fs =
([x,x+2..q-2] `minus`
foldt [[y+s,y+2*s..q] | (s,y) <- fs])
++ sieve ps (q+2) (head ps^2)
((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
foldt (a:xs) = union a (foldt (pairs xs))
foldt [] = []
pairs (a:b:xs) = union a b : pairs xs
pairs xs = xs
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
{- FOLDT (w/ foldr) (w/ foldl)
100,000: 1,299,709 0.23s 6.8MB 0.40s 7.8MB 1.33s 8.8MB
0.5 mln: 7,368,787 1.54s 25.2MB 3.80s 31.3MB 300k:7.35s 19MB
1.0 mln: 15,485,863 3.65s 48.8MB 10.31s 57.0MB 450k:14.1s 28MB
2.0 mln: 32,452,843 8.74s 110.2MB
2.5 mln: 41,161,739 12.02s 134.8MB
O(n^1.28) O(n^1.1) (n^1.41) (n^1.3) (n^1.57) (^2.1)
-}
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzKCkgISEgKHJlYWQgcyAtIDEpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBUUkVFLWZvbGRpbmcgbXVsdGlwbGVzLXVuaW9uCiB3aGVyZSAgICAgICAgICAgICAgICAgICAtLSAgRVJBVE9TdGhlbmVzIHNpZXZlCiAgIHByaW1lcycgID0gMzogc2lldmUgcHJpbWVzJyA1IDkgW10KICAgc2lldmUgKHA6cHMpIHggcSBmcyA9IAogICAgICAgIChbeCx4KzIuLnEtMl0gYG1pbnVzYCAKICAgICAgICAgICAgICAgICAgICAgICAgICBmb2xkdCBbW3krcyx5KzIqcy4ucV0gfCAocyx5KSA8LSBmc10pCiAgICAgICAgKysgc2lldmUgcHMgKHErMikgKGhlYWQgcHNeMikKICAgICAgICAgICAgICgoKysgWygyKnAscSldKSBbKHMscS1yZW0gKHEteSkgcykgfCAocyx5KSA8LSBmc10pCiAgICAKICAgZm9sZHQgKGE6eHMpICAgICA9IHVuaW9uIGEgKGZvbGR0IChwYWlycyB4cykpIAogICBmb2xkdCBbXSAgICAgICAgID0gW10KICAgcGFpcnMgKGE6Yjp4cykgICA9IHVuaW9uIGEgYiA6IHBhaXJzIHhzCiAgIHBhaXJzIHhzICAgICAgICAgPSB4cwogICAKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFUSAtPiB4IDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiBhICB5cwogICB1bmlvbiBhICAgICAgICBbXSAgICAgICA9IGEKICAgdW5pb24gW10gICAgICAgYiAgICAgICAgPSBiCiAgIAogICBtaW51cyBhQCh4OnhzKSBiQCh5OnlzKSA9IGNhc2UgY29tcGFyZSB4IHkgb2YgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBMVCAtPiB4IDogbWludXMgeHMgYgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4gICAgIG1pbnVzIHhzIHlzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBHVCAtPiAgICAgbWludXMgYSAgeXMKICAgbWludXMgYSAgICAgICAgYiAgICAgICAgPSBhCiAgIAp7LSAgICAgICAgICAgICAgICAgICAgICAgICAgIEZPTERUICAgICAgICAgICAgKHcvIGZvbGRyKSAgICAgICAgKHcvIGZvbGRsKQogICAxMDAsMDAwOiAgMSwyOTksNzA5ICAgMC4yM3MgICAgNi44TUIgICAgICAwLjQwcyAgIDcuOE1CICAgICAgMS4zM3MgIDguOE1CCiAgIDAuNSBtbG46ICA3LDM2OCw3ODcgICAxLjU0cyAgIDI1LjJNQiAgICAgIDMuODBzICAzMS4zTUIgICAgMzAwazo3LjM1cyAxOU1CCiAgIDEuMCBtbG46IDE1LDQ4NSw4NjMgICAzLjY1cyAgIDQ4LjhNQiAgICAgMTAuMzFzICA1Ny4wTUIgICAgNDUwazoxNC4xcyAyOE1CCiAgIDIuMCBtbG46IDMyLDQ1Miw4NDMgICA4Ljc0cyAgMTEwLjJNQiAgCiAgIDIuNSBtbG46IDQxLDE2MSw3MzkgIDEyLjAycyAgMTM0LjhNQgogICAKICAgICAgICAgICAgICAgICAgICAgTyhuXjEuMjgpICBPKG5eMS4xKSAgIChuXjEuNDEpIChuXjEuMykgICAobl4xLjU3KSAoXjIuMSkKLX0=