{-# OPTIONS_GHC -O2 -fno-cse #-}
primesTMWE = 2:3:5:7: gapsW 11 wheel (joinT3 $ hitsW 11 wheel primes11)
  where
    primes11 = 11: gapsW 13 (tail wheel) (joinT3 $ hitsW 11 wheel primes11)
 
gapsW k ws@(d:w) cs@(c:u) | k==c      =     gapsW (k+d) w u 
                          | otherwise = k : gapsW (k+d) w cs  
hitsW k ws@(d:w) ps@(p:u) | k==p      = scanl (\c d->c+p*d) (p*p) ws 
                                          : hitsW (k+d) w u 
                          | otherwise =     hitsW (k+d) w ps    
joinT3 ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)    
                                   `union` joinT3 (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
 
main = do 
  x <- read `fmap` getLine         --  100k     1mln     2mln     4mln
  mapM_ print . take 2 .           -- 6.8MB    6.8MB    6.8MB    6.8MB   -- !!!
        map fst . tail .           -- 0.13s    2.09s    4.87s    11.25s
        iterate (splitAt 10.snd)   --     n^1.21   n^1.22   n^1.21       -- !!
        $ ([], drop (x-10) primesTMWE)
 
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

ey0jIE9QVElPTlNfR0hDIC1PMiAtZm5vLWNzZSAjLX0KcHJpbWVzVE1XRSA9IDI6Mzo1Ojc6IGdhcHNXIDExIHdoZWVsIChqb2luVDMgJCBoaXRzVyAxMSB3aGVlbCBwcmltZXMxMSkKICB3aGVyZQogICAgcHJpbWVzMTEgPSAxMTogZ2Fwc1cgMTMgKHRhaWwgd2hlZWwpIChqb2luVDMgJCBoaXRzVyAxMSB3aGVlbCBwcmltZXMxMSkKIApnYXBzVyBrIHdzQChkOncpIGNzQChjOnUpIHwgaz09YyAgICAgID0gICAgIGdhcHNXIChrK2QpIHcgdSAKICAgICAgICAgICAgICAgICAgICAgICAgICB8IG90aGVyd2lzZSA9IGsgOiBnYXBzVyAoaytkKSB3IGNzICAKaGl0c1cgayB3c0AoZDp3KSBwc0AocDp1KSB8IGs9PXAgICAgICA9IHNjYW5sIChcYyBkLT5jK3AqZCkgKHAqcCkgd3MgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDogaGl0c1cgKGsrZCkgdyB1IAogICAgICAgICAgICAgICAgICAgICAgICAgIHwgb3RoZXJ3aXNlID0gICAgIGhpdHNXIChrK2QpIHcgcHMgICAgCmpvaW5UMyAoKHg6eHMpOiB+KHlzOnpzOnQpKSA9IHggOiB1bmlvbiB4cyAodW5pb24geXMgenMpICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGB1bmlvbmAgam9pblQzIChwYWlycyB0KSAgCnBhaXJzICgoeDp4cyk6eXM6dCkgPSAoeCA6IHVuaW9uIHhzIHlzKSA6IHBhaXJzIHQgCndoZWVsID0gMjo0OjI6NDo2OjI6Njo0OjI6NDo2OjY6Mjo2OjQ6Mjo2OjQ6Njo4OjQ6Mjo0OjI6CiAgICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aGVlbAoKbWFpbiA9IGRvIAogIHggPC0gcmVhZCBgZm1hcGAgZ2V0TGluZSAgICAgICAgIC0tICAxMDBrICAgICAxbWxuICAgICAybWxuICAgICA0bWxuCiAgbWFwTV8gcHJpbnQgLiB0YWtlIDIgLiAgICAgICAgICAgLS0gNi44TUIgICAgNi44TUIgICAgNi44TUIgICAgNi44TUIgICAtLSAhISEKICAgICAgICBtYXAgZnN0IC4gdGFpbCAuICAgICAgICAgICAtLSAwLjEzcyAgICAyLjA5cyAgICA0Ljg3cyAgICAxMS4yNXMKICAgICAgICBpdGVyYXRlIChzcGxpdEF0IDEwLnNuZCkgICAtLSAgICAgbl4xLjIxICAgbl4xLjIyICAgbl4xLjIxICAgICAgIC0tICEhCiAgICAgICAgJCAoW10sIGRyb3AgKHgtMTApIHByaW1lc1RNV0UpCgp1bmlvbiAoeDp4cykgKHk6eXMpID0gY2FzZSAoY29tcGFyZSB4IHkpIG9mIAogICAgICAgICAgIExUIC0+IHggOiB1bmlvbiAgeHMgICh5OnlzKQogICAgICAgICAgIEVRIC0+IHggOiB1bmlvbiAgeHMgICAgIHlzIAogICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiAoeDp4cykgIHlz

NDAwMDAwMA==

4000000