{-# OPTIONS_GHC -O2 -fno-cse #-}
module Main where
main = do
tmwprimes = 2:3:5:7:primes' -- tree-merged | primes-multiples removal
where -- | with 2-3-5-7 WHEEL
primes' = roll
11 wheel `minus`
(fst.tfold unionSP
) [([p*p],[p*q|q<-rollFrom p]) | p <- primes_]
primes
_ = h
++ t `minus`
(fst.tfold unionSP
) [([p*p],[p*q|q<-rollFrom p]) | p <- primes_]
where (h
,t
) = splitAt 6 (11:rollFrom
11) -- avoid sharing
tfold f xs = go (pairs xs)
where go (a:b:c:ys) = f a (f b c) `f` go (pairs ys)
pairs (a:b:ys) = f a b : pairs ys
unionSP (a:as,bs) v = (a:x,y) where (x,y)=unionSP (as,bs) v
unionSP u
@([],b:bs
) v
@(c:cs
,ds
) = case compare b c
of LT -> (b:x,y) where (x,y)=unionSP ([],bs) v
EQ -> (b:x,y) where (x,y)=unionSP ([],bs) (cs,ds)
GT -> (c:x,y) where (x,y)=unionSP u (cs,ds)
unionSP ([],bs) ([],ds) = ([] ,union bs ds)
rollFrom n = go wheelNums wheel
where m
= (n
-11) `
mod`
210 go (x:xs) (w:ws) | x==m = roll (n+w) ws
| True = go xs ws
wheelNums = roll 0 wheel -- [0,2,6,8,12,18, ...]
wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
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 b
= if null a
then b
else a
minus a
@(x:xs
) b
@(y:ys
) = case compare x y
of LT -> x: xs `minus` b
EQ -> xs `minus` ys
GT -> a `minus` ys
minus a b = a
ey0jIE9QVElPTlNfR0hDIC1PMiAtZm5vLWNzZSAjLX0KCm1vZHVsZSBNYWluIHdoZXJlCgptYWluID0gZG8KICBtIDwtIGdldExpbmUKICBwdXRTdHIgJCBtICsrICItdGggcHJpbWU6ICIKICBwcmludCAkIHRtd3ByaW1lcyAhISAocmVhZCBtIC0gMSkKCnRtd3ByaW1lcyA6OiBbSW50XQp0bXdwcmltZXMgPSAyOjM6NTo3OnByaW1lcycgICAtLSB0cmVlLW1lcmdlZCB8IHByaW1lcy1tdWx0aXBsZXMgcmVtb3ZhbAogICB3aGVyZSAgICAgICAgICAgICAgICAgICAgIC0tICAgICAgICAgICAgIHwgd2l0aCAyLTMtNS03IFdIRUVMCiAgICBwcmltZXMnICA9IHJvbGwgMTEgd2hlZWwgYG1pbnVzYCAoZnN0LnRmb2xkIHVuaW9uU1ApCiAgICAgICAgICAgICAgICAgWyhbcCpwXSxbcCpxfHE8LXJvbGxGcm9tIHBdKSB8IHAgPC0gcHJpbWVzX10KICAgIHByaW1lc18gID0gaCArKyB0IGBtaW51c2AgKGZzdC50Zm9sZCB1bmlvblNQKQogICAgICAgICAgICAgICAgIFsoW3AqcF0sW3AqcXxxPC1yb2xsRnJvbSBwXSkgfCBwIDwtIHByaW1lc19dCiAgICAgIHdoZXJlIChoLHQpID0gc3BsaXRBdCA2ICgxMTpyb2xsRnJvbSAxMSkgICAgICAgICAgLS0gYXZvaWQgc2hhcmluZwogICAgCiAgICB0Zm9sZCBmIHhzID0gZ28gKHBhaXJzIHhzKQogICAgICB3aGVyZSBnbyAoYTpiOmM6eXMpID0gZiBhIChmIGIgYykgYGZgIGdvIChwYWlycyB5cykKICAgICAgICAgICAgcGFpcnMgKGE6Yjp5cykgPSBmIGEgYiA6IHBhaXJzIHlzCgogICAgdW5pb25TUCAoYTphcyxicykgICB2ICAgPSAoYTp4LHkpICB3aGVyZSAoeCx5KT11bmlvblNQIChhcyxicykgdgogICAgdW5pb25TUCB1QChbXSxiOmJzKSB2QChjOmNzLGRzKSA9IGNhc2UgY29tcGFyZSBiIGMgb2YKICAgICAgICAgICAgICAgICAgICAgICBMVCAtPiAgKGI6eCx5KSAgd2hlcmUgKHgseSk9dW5pb25TUCAoW10sYnMpIHYgCiAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4gIChiOngseSkgIHdoZXJlICh4LHkpPXVuaW9uU1AgKFtdLGJzKSAoY3MsZHMpIAogICAgICAgICAgICAgICAgICAgICAgIEdUIC0+ICAoYzp4LHkpICB3aGVyZSAoeCx5KT11bmlvblNQIHUgICAgICAgKGNzLGRzKQogICAgdW5pb25TUCAoW10sYnMpIChbXSxkcykgPSAoW10gLHVuaW9uIGJzIGRzKQogICAgCiAgICByb2xsRnJvbSBuID0gZ28gd2hlZWxOdW1zIHdoZWVsCiAgICAgIHdoZXJlIG0gPSAobi0xMSkgYG1vZGAgMjEwCiAgICAgICAgICAgIGdvICh4OnhzKSAodzp3cykgfCB4PT1tID0gcm9sbCAobit3KSB3cyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICB8IFRydWUgPSBnbyB4cyB3cwogICAgd2hlZWxOdW1zICA9IHJvbGwgMCB3aGVlbCAgICAgICAgIC0tIFswLDIsNiw4LDEyLDE4LCAuLi5dIAogICAgcm9sbCAgICAgICA9IHNjYW5sICgrKQogICAgd2hlZWwgICAgICA9IDI6NDoyOjQ6NjoyOjY6NDoyOjQ6Njo2OjI6Njo0OjI6Njo0OjY6ODo0OjI6NDoyOgogICAgICAgICAgICAgICAgIDQ6ODo2OjQ6NjoyOjQ6NjoyOjY6Njo0OjI6NDo2OjI6Njo0OjI6NDoyOjEwOjI6MTA6d2hlZWwKICAgIAogICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIExUIC0+IHg6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4geDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBHVCAtPiB5OiB1bmlvbiBhICB5cwogICAgdW5pb24gYSAgICAgICAgYiAgICAgICAgPSBpZiBudWxsIGEgdGhlbiBiIGVsc2UgYQogICAgCiAgICBtaW51cyBhQCh4OnhzKSBiQCh5OnlzKSA9IGNhc2UgY29tcGFyZSB4IHkgb2YgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geDogeHMgYG1pbnVzYCBiCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4gICAgeHMgYG1pbnVzYCB5cwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+ICAgIGEgIGBtaW51c2AgeXMKICAgIG1pbnVzIGEgICAgICAgIGIgICAgICAgID0gYQ==