{-# OPTIONS_GHC -O2 -fno-cse #-}
primesTMWE
= ([2,3,5,7 :: Int]++) . _Y
$ (11:
) . gapsW
13 (tail wheel
) . joinT3
. rollW
11 wheel
_Y g = g (_Y g) -- telescopic
-- g xs where xs = g xs -- two-stage
gapsW k ws@(w:t) cs@(c:u) | k==c = gapsW (k+w) t u
| True = k : gapsW (k+w) t cs
rollW k ws
@(w:t
) ps
@(p:u
) | k
==p
= scanl (\c d
->c
+p
*d
) (p
*p
) ws
: rollW (k+w) t u
| True = rollW (k+w) t ps
joinT3 ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)
`union` joinT3 (pairs t)
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
main = do
. take 2 . map fst -- 0.13s 2.01s 4.67s 10.71s -- [Integer], tele, no -O2 $ ([], drop (x
-10) primesTMWE
) -- 0.08s 1.31s 3.18s 7.93s -- [Int], telescopic
pairs (xs:ys:t) = union xs ys : pairs t -- 0.08s 1.41s 3.36s 7.96s -- [Int], two-stage
union
(x:xs
) (y:ys
) = case (compare x y
) of LT -> x : union xs (y:ys)
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
ey0jIE9QVElPTlNfR0hDIC1PMiAtZm5vLWNzZSAjLX0KcHJpbWVzVE1XRSA9IChbMiwzLDUsNyA6OiBJbnRdKyspIC4gX1kgJCAoMTE6KSAuCiAgICAgICAgICAgICAgICAgICBnYXBzVyAxMyAodGFpbCB3aGVlbCkgLiBqb2luVDMgLiByb2xsVyAxMSB3aGVlbAoKX1kgZyA9IGcgKF9ZIGcpICAgICAgICAgICAgICAgICAgICAgLS0gdGVsZXNjb3BpYwogICAgICAgLS0gZyB4cyB3aGVyZSB4cyA9IGcgeHMgICAgICAtLSB0d28tc3RhZ2UgCiAKZ2Fwc1cgayB3c0Aodzp0KSBjc0AoYzp1KSB8IGs9PWMgID0gZ2Fwc1cgKGsrdykgdCB1IAogICAgICAgICAgICAgICAgICAgICAgICAgIHwgVHJ1ZSAgPSBrIDogZ2Fwc1cgKGsrdykgdCBjcyAgCnJvbGxXIGsgd3NAKHc6dCkgcHNAKHA6dSkgfCBrPT1wICA9IHNjYW5sIChcYyBkLT5jK3AqZCkgKHAqcCkgd3MgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgOiByb2xsVyAoayt3KSB0IHUgCiAgICAgICAgICAgICAgICAgICAgICAgICAgfCBUcnVlICA9IHJvbGxXIChrK3cpIHQgcHMgICAgCmpvaW5UMyAoKHg6eHMpOiB+KHlzOnpzOnQpKSA9IHggOiB1bmlvbiB4cyAodW5pb24geXMgenMpICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGB1bmlvbmAgam9pblQzIChwYWlycyB0KSAgCndoZWVsID0gMjo0OjI6NDo2OjI6Njo0OjI6NDo2OjY6Mjo2OjQ6Mjo2OjQ6Njo4OjQ6Mjo0OjI6CiAgICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aGVlbAoKbWFpbiA9IGRvIAogICB4IDwtIHJlYWQgYGZtYXBgIGdldExpbmUgICAgICAgICAgICAgICAgLS0gICAxMDBrICAgIDFtbG4gICAgIDJtbG4gICAgIDRtbG4KICAgbWFwTV8gcHJpbnQgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC0tICA2LjhNQiAgIDYuOE1CICAgIDYuOE1CICAgIDYuOE1CICAgICAtLSAhISEhIQogICAgICAgICAuIHRha2UgMiAuIG1hcCBmc3QgICAgICAgICAgICAgICAgLS0gIDAuMTNzICAgMi4wMXMgICAgNC42N3MgICAgMTAuNzFzICAgIC0tIFtJbnRlZ2VyXSwgdGVsZSwgbm8gLU8yCiAgICAgICAgIC4gdGFpbCAuIGl0ZXJhdGUgKHNwbGl0QXQgMTAuc25kKSAtLSAgICAgIG5eMS4xOSAgbl4xLjIyICAgbl4xLjIwICAgICAgICAgLS0gISEhIQogICAgICAgICAkIChbXSwgZHJvcCAoeC0xMCkgcHJpbWVzVE1XRSkgICAgLS0gIDAuMDhzICAgMS4zMXMgICAgMy4xOHMgICAgIDcuOTNzICAgIC0tIFtJbnRdLCB0ZWxlc2NvcGljCgpwYWlycyAoeHM6eXM6dCkgPSB1bmlvbiB4cyB5cyA6IHBhaXJzIHQgICAgLS0gIDAuMDhzICAgMS40MXMgICAgMy4zNnMgICAgIDcuOTZzICAgIC0tIFtJbnRdLCB0d28tc3RhZ2UKdW5pb24gKHg6eHMpICh5OnlzKSA9IGNhc2UgKGNvbXBhcmUgeCB5KSBvZiAKICAgICAgICAgICBMVCAtPiB4IDogdW5pb24gIHhzICAoeTp5cykKICAgICAgICAgICBFUSAtPiB4IDogdW5pb24gIHhzICAgICB5cyAKICAgICAgICAgICBHVCAtPiB5IDogdW5pb24gKHg6eHMpICB5cw==
[1299553,1299583,1299601,1299631,1299637,1299647,1299653,1299673,1299689,1299709]
[1299721,1299743,1299763,1299791,1299811,1299817,1299821,1299827,1299833,1299841]