{-# OPTIONS_GHC -O2 -fno-cse #-}
primes
:: [Int] -- wheeled gaps on treefold-joined wheeled primes' multiplesprimes = 2:3:5:7: gaps 11 wheel (join $ roll 11 wheel primes_)
where
primes
_ = 11: gaps
13 (tail wheel
) (join $ roll 11 wheel primes_)
gaps k ws@(w:t) cs@(c:u) | k==c = gaps (k+w) t u
| True = k : gaps (k+w) t cs -- k<c
roll k ws
@(w:t
) ps
@(p:u
) | k
==p
= scanl (\c d
->c
+p
*d
) (p
*p
) ws
: roll (k+w) t u
| True = roll (k+w) t ps -- k<p
join ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)
`union` join (pairs t)
pairs ((x:xs):ys:t) = (x : union xs ys) : 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
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
{-
Tree Merged Multiples Re-moval: O(n^1.24) speed, O(1) space:
--- simple_tfold ---- two-feed ------ wheel ------ 3/2 tfold -- gaps/roll
1M 4.09s _47.8MB -- 3.28s 4.7MB -- 1.95s 5.8MB -- 1.90s 4.8MB -- 1.38s ---
2M 9.86s 111.2MB -- 7.66s 4.7MB -- 4.68s 5.8MB -- 4.48s 4.8MB -- 3.25s ---
3M ------------------------------------------------------------- 5.40s ---
4M 7.68s - 4.7M
5M 10.08s - 4.7M
6M 12.66s - 4.7M
O(n^1.24)
-}
(map (12.66/) [1.38,3.25,5.40,7.68,10.08])
IHstIyBPUFRJT05TX0dIQyAtTzIgLWZuby1jc2UgIy19Cm1haW4gPSBnZXRMaW5lID4+PSBwcmludCAuIChwcmltZXMgISEpIC4gKCsgKC0xKSkgLiByZWFkCgpwcmltZXMgOjogW0ludF0gIC0tIHdoZWVsZWQgZ2FwcyBvbiB0cmVlZm9sZC1qb2luZWQgd2hlZWxlZCBwcmltZXMnIG11bHRpcGxlcwpwcmltZXMgPSAyOjM6NTo3OiBnYXBzIDExIHdoZWVsIChqb2luICQgcm9sbCAxMSB3aGVlbCBwcmltZXNfKQogd2hlcmUKICAgcHJpbWVzXyA9IDExOiBnYXBzIDEzICh0YWlsIHdoZWVsKSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoam9pbiAkIHJvbGwgMTEgd2hlZWwgcHJpbWVzXykKCiAgIGdhcHMgayB3c0Aodzp0KSBjc0AoYzp1KSB8IGs9PWMgID0gZ2FwcyAoayt3KSB0IHUgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB8IFRydWUgID0gayA6IGdhcHMgKGsrdykgdCBjcyAgICAgLS0gazxjCgogICByb2xsIGsgd3NAKHc6dCkgcHNAKHA6dSkgfCBrPT1wICA9IHNjYW5sIChcYyBkLT5jK3AqZCkgKHAqcCkgd3MgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA6IHJvbGwgKGsrdykgdCB1IAogICAgICAgICAgICAgICAgICAgICAgICAgICAgfCBUcnVlICA9IHJvbGwgKGsrdykgdCBwcyAgICAgICAgIC0tIGs8cCAKCiAgIGpvaW4gKCh4OnhzKTogfih5czp6czp0KSkgPSB4IDogdW5pb24geHMgKHVuaW9uIHlzIHpzKSAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBgdW5pb25gIGpvaW4gKHBhaXJzIHQpICAKICAgcGFpcnMgKCh4OnhzKTp5czp0KSAgICAgICA9ICh4IDogdW5pb24geHMgeXMpIDogcGFpcnMgdAogICAgCiAgIHdoZWVsID0gMjo0OjI6NDo2OjI6Njo0OjI6NDo2OjY6Mjo2OjQ6Mjo2OjQ6Njo4OjQ6Mjo0OjI6CiAgICAgICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aGVlbAogICAKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mCiAgICAgIExUIC0+IHg6IHVuaW9uIHhzIGIKICAgICAgRVEgLT4geDogdW5pb24geHMgeXMKICAgICAgR1QgLT4geTogdW5pb24gYSAgeXMKey0KVHJlZSBNZXJnZWQgTXVsdGlwbGVzIFJlLW1vdmFsOiAgTyhuXjEuMjQpIHNwZWVkLCBPKDEpIHNwYWNlOgoKLS0tIHNpbXBsZV90Zm9sZCAtLS0tIHR3by1mZWVkIC0tLS0tLSB3aGVlbCAtLS0tLS0gMy8yIHRmb2xkIC0tIGdhcHMvcm9sbAoxTSA0LjA5cyBfNDcuOE1CIC0tIDMuMjhzIDQuN01CIC0tIDEuOTVzIDUuOE1CIC0tIDEuOTBzIDQuOE1CIC0tIDEuMzhzIC0tLQoyTSA5Ljg2cyAxMTEuMk1CIC0tIDcuNjZzIDQuN01CIC0tIDQuNjhzIDUuOE1CIC0tIDQuNDhzIDQuOE1CIC0tIDMuMjVzIC0tLQozTSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIDUuNDBzIC0tLQo0TSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDcuNjhzIC0gNC43TQo1TSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTAuMDhzIC0gNC43TQo2TSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTIuNjZzIC0gNC43TQoKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTyhuXjEuMjQpCi19CgptYWluMiA9IG1hcE1fIHByaW50ICQgemlwV2l0aCBsb2dCYXNlIChtYXAgKDYvKSBbMS4uNV0pCiAgICAgICAgICAgICAgICAgICAgICAobWFwICgxMi42Ni8pIFsxLjM4LDMuMjUsNS40MCw3LjY4LDEwLjA4XSkK