import Data.List     -- stackoverflow.com/q/33531834
import Data.Function (fix)

main1 = print . take 100 . nubBy (\x y -> x `rem` y == 0) $ [2..]
main2 = print . take 100 . nubBy (\x y -> x `gcd` y > 1) $ [2..]

  -- stackoverflow.com/a/36668089
  -- stackoverflow.com/a/36725003
foldi1 f (h:t) = f h . foldi1 f . unfoldr (\(a:b:r)-> Just (f a b, r)) $ t
                       
ps1=2 : fix ((3:) . concat . unfoldr (\(x,u:us)-> Just ([x|u==0], (x+2,us))) 
            . (,) 5 . ([0,0] ++) 
            . foldi1 (\(x:xs) ys -> let n=div (head ys - x) 2 - 1 in
                          x:take n xs ++ zipWith max ys (drop n xs))
            . map (\p-> (p*p :) . tail . cycle $ 1 : replicate (p-1) 0) )

main = print . take 10 . drop 80000 $ ps    -- 40k ps1:1.88s ps:1.20s
                                            -- 80k     5.52     3.68
-- which is to say,                         --        n^1.6    n^1.6

no_compos x (u:us) = [x | u==0] ++ no_compos (x+2) us
foldi f (h:t) = f h . foldi f . pairs f $ t
pairs f (a:b:r) = f a b : pairs f r
mjoin (x:xs) ys = x : after (div (head ys - x) 2 - 1) xs (zipWith max ys) 
after n xs k | n>0 = head xs : after (n-1) (tail xs) k  
             | otherwise = k xs                         
mults p = (p*p :) . tail . cycle $ 1 : replicate (p-1) 0
ps = 2 : ops where
         ops = 3:5:7:(no_compos 9 . foldi mjoin . map mults) ops