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