{-# OPTIONS_GHC -O2 #-}
module Main where
import Data.List (tails)  
main = print $ primes !! 1000000    --  -fno-cse -fno-full-laziness 
 
primes0 = _Y $ (2:) . minus [3..] . 
              foldr (\p-> (p*p :) . union [p*p+p, p*p+2*p..]) []
 
primes :: [Int]
primes = [2,3,5,7] ++ _Y ((11:) . tail . minus (scanl (+) 11 wh11) 
                   . foldi (\(x:xs)-> (x:) . union xs)
                   . map (\(w,p)-> scanl (\c d-> c + p*d) (p*p) w)
                   . equalsBy snd (tails wh11 `zip` scanl (+) 11 wh11))
 
wh3  = 2:wh3                 --  ([3],2)                {1*2,2*3}
wh5  = 2:4:wh5               --  ([5,7],6)                  {2*4,6*5}
wh7  = 4:2:4:2:4:6:2:6:wh7   --  ([7,11,13,17,19,23,29,31],30)  {8*6,30*7}
wh11 = 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:wh11
_Y g = g (_Y g)        -- multistage with non-sharing fixpoint combinator
     -- = g (fix g)    -- two stages with sharing fixpoint combinator
 
foldi f (xs:t) = f xs . foldi f . pairs f $ t
pairs f (x:y:t) = f x y : pairs f t
 
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  
minus a@(x:xs) b@(y:ys) = case compare x y of 
         LT -> x : minus  xs b   
         EQ ->     minus  xs ys  
         GT ->     minus  a  ys  
equalsBy f a@(x:xs) b@(y:ys) = case compare (f x) y of 
         LT ->     equalsBy f  xs b   
         EQ -> x : equalsBy f  xs ys  
         GT ->     equalsBy f  a  ys

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKaW1wb3J0IERhdGEuTGlzdCAodGFpbHMpICAKbWFpbiA9IHByaW50ICQgcHJpbWVzICEhIDEwMDAwMDAgICAgLS0gIC1mbm8tY3NlIC1mbm8tZnVsbC1sYXppbmVzcyAKCnByaW1lczAgPSBfWSAkICgyOikgLiBtaW51cyBbMy4uXSAuIAogICAgICAgICAgICAgIGZvbGRyIChccC0+IChwKnAgOikgLiB1bmlvbiBbcCpwK3AsIHAqcCsyKnAuLl0pIFtdCgpwcmltZXMgOjogW0ludF0KcHJpbWVzID0gWzIsMyw1LDddICsrIF9ZICgoMTE6KSAuIHRhaWwgLiBtaW51cyAoc2NhbmwgKCspIDExIHdoMTEpIAogICAgICAgICAgICAgICAgICAgLiBmb2xkaSAoXCh4OnhzKS0+ICh4OikgLiB1bmlvbiB4cykKICAgICAgICAgICAgICAgICAgIC4gbWFwIChcKHcscCktPiBzY2FubCAoXGMgZC0+IGMgKyBwKmQpIChwKnApIHcpCiAgICAgICAgICAgICAgICAgICAuIGVxdWFsc0J5IHNuZCAodGFpbHMgd2gxMSBgemlwYCBzY2FubCAoKykgMTEgd2gxMSkpCiAgICAgICAgICAgICAgICAgICAKd2gzICA9IDI6d2gzICAgICAgICAgICAgICAgICAtLSAgKFszXSwyKSAgICAgICAgICAgICAgICB7MSoyLDIqM30Kd2g1ICA9IDI6NDp3aDUgICAgICAgICAgICAgICAtLSAgKFs1LDddLDYpICAgICAgICAgICAgICAgICAgezIqNCw2KjV9CndoNyAgPSA0OjI6NDoyOjQ6NjoyOjY6d2g3ICAgLS0gIChbNywxMSwxMywxNywxOSwyMywyOSwzMV0sMzApICB7OCo2LDMwKjd9CndoMTEgPSAyOjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjY6NjoyOjY6NDoyOjY6NDo2Ojg6NDoyOjQ6MjogIAogICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aDExCl9ZIGcgPSBnIChfWSBnKSAgICAgICAgLS0gbXVsdGlzdGFnZSB3aXRoIG5vbi1zaGFyaW5nIGZpeHBvaW50IGNvbWJpbmF0b3IKICAgICAtLSA9IGcgKGZpeCBnKSAgICAtLSB0d28gc3RhZ2VzIHdpdGggc2hhcmluZyBmaXhwb2ludCBjb21iaW5hdG9yCgpmb2xkaSBmICh4czp0KSA9IGYgeHMgLiBmb2xkaSBmIC4gcGFpcnMgZiAkIHQKcGFpcnMgZiAoeDp5OnQpID0gZiB4IHkgOiBwYWlycyBmIHQKCnVuaW9uIGFAKHg6eHMpIGJAKHk6eXMpID0gY2FzZSBjb21wYXJlIHggeSBvZiAKICAgICAgICAgTFQgLT4geCA6IHVuaW9uICB4cyBiICAgCiAgICAgICAgIEVRIC0+IHggOiB1bmlvbiAgeHMgeXMgIAogICAgICAgICBHVCAtPiB5IDogdW5pb24gIGEgIHlzICAKbWludXMgYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICBMVCAtPiB4IDogbWludXMgIHhzIGIgICAKICAgICAgICAgRVEgLT4gICAgIG1pbnVzICB4cyB5cyAgCiAgICAgICAgIEdUIC0+ICAgICBtaW51cyAgYSAgeXMgIAplcXVhbHNCeSBmIGFAKHg6eHMpIGJAKHk6eXMpID0gY2FzZSBjb21wYXJlIChmIHgpIHkgb2YgCiAgICAgICAgIExUIC0+ICAgICBlcXVhbHNCeSBmICB4cyBiICAgCiAgICAgICAgIEVRIC0+IHggOiBlcXVhbHNCeSBmICB4cyB5cyAgCiAgICAgICAgIEdUIC0+ICAgICBlcXVhbHNCeSBmICBhICB5cw==

MW1sbjogMi41MHMgLSA5LjQgTSAgICAgICAgICAgICAgICAgIG9yZG1lcmdlQnkgOiA0LjQ0cyAtIDkuNCBNCjJtbG46IDUuOTBzIC0gOS4zIE0gICAgIG5eMS4yNCAgICAgICAgICAgICAgICAgICAgOS45MXMgLSA5LjQgTSAgICBuXjEuMTYKM21sbjogOS4yOXMgLSA5LjQgTSAgICAgbl4xLjEyCgotLSBzb21ldGhpbmcgY2hhbmdlZCBvbiAyMDEzLTA3LTMxOgotLSBzdWRkZW5seSBgbWludXMgKHNjYW5sICgrKSAxMSB3aDExKWAgZG9lc24ndCBjYXVzZSBIVUdFIHNwYWNlIGxlYWsgYW55bW9yZSAhPz8hIQotLSAgYW5kIHJ1bnMgc2xvd2VyIHRoYXQgZ2Fwcy9oaXRzIChzZWUgdmtYQ1h0KS4gLS0gSURFT05FIFNXSVRDSEVEIGZyb20gNy40LjEgdG8gNy42LjMgIS4uLi4KLS0gKG1hcCAocCopICQgc2NhbmwgKCspIHAgdyk6IDMuMTVzIC4uLiA2LjkxcyAsIDkuMyBNQiAgIG5eMS4xMwoKLS0gLi4uLi4uIGFuZCBpbiA3LjguMyBpdCBMRUFLUyBBR0FJTiBsaWtlIGNyYXp5ISEgICBvbmx5IGdhcHMvaGl0cyBkb2Vzbid0IGxlYWs=

1mln: 2.50s - 9.4 M                  ordmergeBy : 4.44s - 9.4 M
2mln: 5.90s - 9.3 M     n^1.24                    9.91s - 9.4 M    n^1.16
3mln: 9.29s - 9.4 M     n^1.12

-- something changed on 2013-07-31:
-- suddenly `minus (scanl (+) 11 wh11)` doesn't cause HUGE space leak anymore !??!!
--  and runs slower that gaps/hits (see vkXCXt). -- IDEONE SWITCHED from 7.4.1 to 7.6.3 !....
-- (map (p*) $ scanl (+) p w): 3.15s ... 6.91s , 9.3 MB   n^1.13

-- ...... and in 7.8.3 it LEAKS AGAIN like crazy!!   only gaps/hits doesn't leak