{-# OPTIONS_GHC -O2 #-} -- unbounded merging idea due to Richard Bird module Main where -- double staged production idea due to Melissa O'Neill -- tree folding idea Dave Bayer / Heinrich Apfelmus main = -- simplified formulation by Will Ness do s <- getLine -- logBase (n2/n1) (t2/t1): ~ n^1.20 print $ take 5 $ drop (read s-5) primes primes :: [Int] primes = 2 : _Y ((3:) . gaps 5 . _U . map (\x-> [x*x, x*x+2*x..])) _Y g = g (_Y g) -- telescoping feed (recursive) -- = g xs where xs = g xs -- double feed (corecursive, sharing) gaps k s@(x:xs) | k < x = k : gaps (k+2) s -- ~= [k,k+2..]\\s , | otherwise = gaps (k+2) xs -- when s⊂[k,k+2..] _U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat 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