{-# OPTIONS_GHC -O2 #-}
main = print $ primes !! 1000000
 
primes :: [Int]
primes = 2 : _Y( (3:) . sieve 5 . unionAll . map (\p->[p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                       -- non-sharing fixpoint combinator
 
    unionAll ((x:xs):t) = x : (union xs . unionAll . pairs) t
    pairs (xs:ys:t) = union xs ys : pairs t
    sieve k s@(x:xs) | k<x  = k : sieve (k+2) s    -- equivalent to
                     | True =     sieve (k+2) xs   --  [k,k+2..]`minus`s, k<=x
 
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

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbWFpbiA9IHByaW50ICQgcHJpbWVzICEhIDEwMDAwMDAKCnByaW1lcyA6OiBbSW50XQpwcmltZXMgPSAyIDogX1koICgzOikgLiBzaWV2ZSA1IC4gdW5pb25BbGwgLiBtYXAgKFxwLT5bcCpwLCBwKnArMipwLi5dKSApCiAgd2hlcmUKICAgIF9ZIGcgPSBnIChfWSBnKSAgICAgICAgICAgICAgICAgICAgICAgLS0gbm9uLXNoYXJpbmcgZml4cG9pbnQgY29tYmluYXRvcgoKICAgIHVuaW9uQWxsICgoeDp4cyk6dCkgPSB4IDogKHVuaW9uIHhzIC4gdW5pb25BbGwgLiBwYWlycykgdAogICAgcGFpcnMgKHhzOnlzOnQpID0gdW5pb24geHMgeXMgOiBwYWlycyB0CiAgICBzaWV2ZSBrIHNAKHg6eHMpIHwgazx4ICA9IGsgOiBzaWV2ZSAoaysyKSBzICAgIC0tIGVxdWl2YWxlbnQgdG8KICAgICAgICAgICAgICAgICAgICAgfCBUcnVlID0gICAgIHNpZXZlIChrKzIpIHhzICAgLS0gIFtrLGsrMi4uXWBtaW51c2BzLCBrPD14Cgp1bmlvbiAoeDp4cykgKHk6eXMpID0gY2FzZSBjb21wYXJlIHggeSBvZiAKICAgICAgICAgTFQgLT4geCA6IHVuaW9uICB4cyAoeTp5cykgCiAgICAgICAgIEVRIC0+IHggOiB1bmlvbiAgeHMgICAgeXMgCiAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiAoeDp4cykgeXM=

MTAwazogIDAuMjVzICA2LjggTUIKMjAwazogIDAuNTdzICA2LjggTUIgICAgbl4xLjE5ICAgICAgLS0gdGltaW5ncyBmb3Igb2Rkczo6W0ludGVnZXJdLCBubyAtTzIKNDAwazogIDEuMzFzICA2LjcgTUIgICAgbl4xLjIwCjgwMGs6ICAzLjA1cyAgNi43IE1CICAgIG5eMS4yMgoxbWxuOiAgNC4wMXMgIDYuNyBNQiAgICBuXjEuMjIKMS41bTogIDYuNTNzICA2LjcgTUIgICAgbl4xLjIw

100k:  0.25s  6.8 MB
200k:  0.57s  6.8 MB    n^1.19      -- timings for odds::[Integer], no -O2
400k:  1.31s  6.7 MB    n^1.20
800k:  3.05s  6.7 MB    n^1.22
1mln:  4.01s  6.7 MB    n^1.22
1.5m:  6.53s  6.7 MB    n^1.20