{-# OPTIONS_GHC -O2 #-}
module Main where
main = print $ primes !! 1000000    --  -fno-cse -fno-full-laziness 
 
primes :: [Int]
primes = [2,3,5,7] ++ _Y ((11:) . tail        -- no leak on 7.8.3 either
                   . gaps 11 wh11 
                   . _U . map (\(w,p)->scanl (\c x-> c+p*x) (p*p) w)
                   . hits 11 wh11)
  where
    gaps k (d:w) s@(c:t) | k < c     = k       : gaps (k+d) w s
                         | otherwise =           gaps (k+d) w t   -- k==c
    hits k (d:w) s@(p:t) | k < p     =           hits (k+d) w s
                         | otherwise = (d:w,p) : hits (k+d) w t   -- k==p
 
_Y g = g (_Y g)        -- multistage with non-sharing fixpoint combinator
     -- = g (fix g)    -- two stages with sharing fixpoint combinator
 
_U ((x:xs):t)   = x : (union xs . _U . pairs) t 
  where
        pairs (xs:ys:t) = union xs ys : pairs 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  
 
wh3  = 2:wh3                -- n=1, d=2  [3, 5..] \\ ((3*) <$> _) 
wh5  = 2:4:wh5              -- n=2, d=6   [5,7,_, 11,..] \\ ((5*) <$> _)  
wh7  = 4:2:4:2:4:6:2:6:wh7  -- n=8,  d=30   [7,11,13,17,19,23,_,29,31,_, 37..]
wh11 =                      -- n=48, d=210                \\ ((7*) <$> _)
       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  
 
primes2 = [2,3,5,7] ++ _Y ((11:) . tail . gaps (scanl (+) 11 wh11)
                                 . _U   . hits (scanl (+) 11 wh11))
  where
    gaps (n:w) s@(c:t) | n < c     = n              : gaps w s
                       | otherwise =                  gaps w t   -- k==c
    hits (n:w) s@(p:t) | n < p     =                  hits w s
                       | otherwise = map (p*) (p:w) : hits w t   -- n==p
      -- almost the same as Dave Bayer's code except here  _^_  he has, in effect,
      -- ~~~~~~                           (filter ((/=0).(`rem`p)) w)
      --    (and also, he doesn't sync on primes, since he uses the filter)
      --   see www.haskell.org/pipermail/haskell-cafe/2007-July/029077.html
    wo_hits_Bayer (n:w) (p:t) = map (p*) (p:w) :           
                          wo_hits_Bayer (filter ((/=0).(`rem`p)) w) t  
    -- also, he uses diff, but
    --  gaps a b == diff a b when b ⊂ a   is more efficient 
 
    -- but most importantly he names a lot of stuff, and thus creates
    -- and re-uses a lot of shared structure; in my code data separation
    -- is the goal, which enables definitions of gaps/hits be fused w/ scanl
 
{-  gaps ~= minus 
    hits ~= equalsBy 
     see  ideone.com/nuoLUE, rHJ9ub -} 

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKbWFpbiA9IHByaW50ICQgcHJpbWVzICEhIDEwMDAwMDAgICAgLS0gIC1mbm8tY3NlIC1mbm8tZnVsbC1sYXppbmVzcyAKCnByaW1lcyA6OiBbSW50XQpwcmltZXMgPSBbMiwzLDUsN10gKysgX1kgKCgxMTopIC4gdGFpbCAgICAgICAgLS0gbm8gbGVhayBvbiA3LjguMyBlaXRoZXIKICAgICAgICAgICAgICAgICAgIC4gZ2FwcyAxMSB3aDExIAogICAgICAgICAgICAgICAgICAgLiBfVSAuIG1hcCAoXCh3LHApLT5zY2FubCAoXGMgeC0+IGMrcCp4KSAocCpwKSB3KQogICAgICAgICAgICAgICAgICAgLiBoaXRzIDExIHdoMTEpCiAgd2hlcmUKICAgIGdhcHMgayAoZDp3KSBzQChjOnQpIHwgayA8IGMgICAgID0gayAgICAgICA6IGdhcHMgKGsrZCkgdyBzCiAgICAgICAgICAgICAgICAgICAgICAgICB8IG90aGVyd2lzZSA9ICAgICAgICAgICBnYXBzIChrK2QpIHcgdCAgIC0tIGs9PWMKICAgIGhpdHMgayAoZDp3KSBzQChwOnQpIHwgayA8IHAgICAgID0gICAgICAgICAgIGhpdHMgKGsrZCkgdyBzCiAgICAgICAgICAgICAgICAgICAgICAgICB8IG90aGVyd2lzZSA9IChkOncscCkgOiBoaXRzIChrK2QpIHcgdCAgIC0tIGs9PXAKCl9ZIGcgPSBnIChfWSBnKSAgICAgICAgLS0gbXVsdGlzdGFnZSB3aXRoIG5vbi1zaGFyaW5nIGZpeHBvaW50IGNvbWJpbmF0b3IKICAgICAtLSA9IGcgKGZpeCBnKSAgICAtLSB0d28gc3RhZ2VzIHdpdGggc2hhcmluZyBmaXhwb2ludCBjb21iaW5hdG9yCgpfVSAoKHg6eHMpOnQpICAgPSB4IDogKHVuaW9uIHhzIC4gX1UgLiBwYWlycykgdCAKICB3aGVyZQogICAgICAgIHBhaXJzICh4czp5czp0KSA9IHVuaW9uIHhzIHlzIDogcGFpcnMgdAoKdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBMVCAtPiB4IDogdW5pb24gIHhzIGIgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4geCA6IHVuaW9uICB4cyB5cyAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiAgYSAgeXMgIAoKd2gzICA9IDI6d2gzICAgICAgICAgICAgICAgIC0tIG49MSwgZD0yICBbMywgNS4uXSBcXCAoKDMqKSA8JD4gXykgCndoNSAgPSAyOjQ6d2g1ICAgICAgICAgICAgICAtLSBuPTIsIGQ9NiAgIFs1LDcsXywgMTEsLi5dIFxcICgoNSopIDwkPiBfKSAgCndoNyAgPSA0OjI6NDoyOjQ6NjoyOjY6d2g3ICAtLSBuPTgsICBkPTMwICAgWzcsMTEsMTMsMTcsMTksMjMsXywyOSwzMSxfLCAzNy4uXQp3aDExID0gICAgICAgICAgICAgICAgICAgICAgLS0gbj00OCwgZD0yMTAgICAgICAgICAgICAgICAgXFwgKCg3KikgPCQ+IF8pCiAgICAgICAyOjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjY6NjoyOjY6NDoyOjY6NDo2Ojg6NDoyOjQ6MjogIAogICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aDExICAKICAgICAgIApwcmltZXMyID0gWzIsMyw1LDddICsrIF9ZICgoMTE6KSAuIHRhaWwgLiBnYXBzIChzY2FubCAoKykgMTEgd2gxMSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLiBfVSAgIC4gaGl0cyAoc2NhbmwgKCspIDExIHdoMTEpKQogIHdoZXJlCiAgICBnYXBzIChuOncpIHNAKGM6dCkgfCBuIDwgYyAgICAgPSBuICAgICAgICAgICAgICA6IGdhcHMgdyBzCiAgICAgICAgICAgICAgICAgICAgICAgfCBvdGhlcndpc2UgPSAgICAgICAgICAgICAgICAgIGdhcHMgdyB0ICAgLS0gaz09YwogICAgaGl0cyAobjp3KSBzQChwOnQpIHwgbiA8IHAgICAgID0gICAgICAgICAgICAgICAgICBoaXRzIHcgcwogICAgICAgICAgICAgICAgICAgICAgIHwgb3RoZXJ3aXNlID0gbWFwIChwKikgKHA6dykgOiBoaXRzIHcgdCAgIC0tIG49PXAKICAgICAgLS0gYWxtb3N0IHRoZSBzYW1lIGFzIERhdmUgQmF5ZXIncyBjb2RlIGV4Y2VwdCBoZXJlICBfXl8gIGhlIGhhcywgaW4gZWZmZWN0LAogICAgICAtLSB+fn5+fn4gICAgICAgICAgICAgICAgICAgICAgICAgICAoZmlsdGVyICgoLz0wKS4oYHJlbWBwKSkgdykKICAgICAgLS0gICAgKGFuZCBhbHNvLCBoZSBkb2Vzbid0IHN5bmMgb24gcHJpbWVzLCBzaW5jZSBoZSB1c2VzIHRoZSBmaWx0ZXIpCiAgICAgIC0tICAgc2VlIHd3dy5oYXNrZWxsLm9yZy9waXBlcm1haWwvaGFza2VsbC1jYWZlLzIwMDctSnVseS8wMjkwNzcuaHRtbAogICAgd29faGl0c19CYXllciAobjp3KSAocDp0KSA9IG1hcCAocCopIChwOncpIDogICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgIHdvX2hpdHNfQmF5ZXIgKGZpbHRlciAoKC89MCkuKGByZW1gcCkpIHcpIHQgIAogICAgLS0gYWxzbywgaGUgdXNlcyBkaWZmLCBidXQKICAgIC0tICBnYXBzIGEgYiA9PSBkaWZmIGEgYiB3aGVuIGIg4oqCIGEgICBpcyBtb3JlIGVmZmljaWVudCAKICAgIAogICAgLS0gYnV0IG1vc3QgaW1wb3J0YW50bHkgaGUgbmFtZXMgYSBsb3Qgb2Ygc3R1ZmYsIGFuZCB0aHVzIGNyZWF0ZXMKICAgIC0tIGFuZCByZS11c2VzIGEgbG90IG9mIHNoYXJlZCBzdHJ1Y3R1cmU7IGluIG15IGNvZGUgZGF0YSBzZXBhcmF0aW9uCiAgICAtLSBpcyB0aGUgZ29hbCwgd2hpY2ggZW5hYmxlcyBkZWZpbml0aW9ucyBvZiBnYXBzL2hpdHMgYmUgZnVzZWQgdy8gc2NhbmwKCnstICBnYXBzIH49IG1pbnVzIAogICAgaGl0cyB+PSBlcXVhbHNCeSAKICAgICBzZWUgIGlkZW9uZS5jb20vbnVvTFVFLCBySEo5dWIgLX0g

MSBtbG46IDE1NDg1ODY3ICAxLjQxcyAtIDcuMyBNQiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCjIgbWxuOiAzMjQ1Mjg2NyAgMy4zMnMgLSA3LjMgTUIgICBuXjEuMjQgICAgICAgICAgICAgICAgCjMgbWxuOiA0OTk3OTY5MyAgNS41NHMgLSA3LjMgTUIgICBuXjEuMjYgMS4yNSAgICAgICAgCjQgbWxuOiA2Nzg2Nzk3OSAgNy45MXMgLSA3LjMgTUIgICBuXjEuMjQgCjYgbWxuOiAxMDQzOTUzMDMgIDEzLjBzLSA3LjMgTUIgICBuXjEuMjMKCnByaW1lczI6CjEgbWxuOiAxNTQ4NTg2NyAgICAgIDIuNTRzIC0gOS4zTUIgICAgMS44eCAgICAgICAgICgyLjk5cyB3L0JheWVyJ3MgJnF1b3Q7ZmlsdGVyJnF1b3Q7KQoyIG1sbjogMzI0NTI4NjcgICAgICA1Ljk3cyAtIDkuNE1CICAgIDEuOHggICAgICg1LjY4KSAgICAgICA1LjA1cy05LjRNQiBXUk5HX0FOU1dSICAgIAozIG1sbjogNDk5Nzk2OTMgICAgICA5Ljg2cyAtIDkuM01CICAgIDEuOHggICAgICAgIG9yICAgICAgIDUuMDlzLTI0NSghKU1CIFJUX0VSUk9SCjQgbWxuOiA2Nzg2Nzk3OSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAxMS4zMXMtNTU0KCEpTUIgUlRfRVJST1IKLS0tLS0tIHBlcmhhcHMgSWRlb25lIGhhcyBUV08gc2V0cyBvZiBzZXJ2ZXJzIHdpdGggVFdPIGRpZmZlcmVudCBHSEMgdmVyc2lvbnMgb3IgZmxhZ3Mgb3Igc29tZXRoaW5n

1 mln: 15485867  1.41s - 7.3 MB                             
2 mln: 32452867  3.32s - 7.3 MB   n^1.24                
3 mln: 49979693  5.54s - 7.3 MB   n^1.26 1.25        
4 mln: 67867979  7.91s - 7.3 MB   n^1.24 
6 mln: 104395303  13.0s- 7.3 MB   n^1.23

primes2:
1 mln: 15485867      2.54s - 9.3MB    1.8x         (2.99s w/Bayer's "filter")
2 mln: 32452867      5.97s - 9.4MB    1.8x     (5.68)       5.05s-9.4MB WRNG_ANSWR    
3 mln: 49979693      9.86s - 9.3MB    1.8x        or       5.09s-245(!)MB RT_ERROR
4 mln: 67867979                                                       11.31s-554(!)MB RT_ERROR
------ perhaps Ideone has TWO sets of servers with TWO different GHC versions or flags or something