{-# 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