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 

aW1wb3J0IERhdGEuTGlzdCAgICAgLS0gc3RhY2tvdmVyZmxvdy5jb20vcS8zMzUzMTgzNAppbXBvcnQgRGF0YS5GdW5jdGlvbiAoZml4KQoKbWFpbjEgPSBwcmludCAuIHRha2UgMTAwIC4gbnViQnkgKFx4IHkgLT4geCBgcmVtYCB5ID09IDApICQgWzIuLl0KbWFpbjIgPSBwcmludCAuIHRha2UgMTAwIC4gbnViQnkgKFx4IHkgLT4geCBgZ2NkYCB5ID4gMSkgJCBbMi4uXQoKICAtLSBzdGFja292ZXJmbG93LmNvbS9hLzM2NjY4MDg5CiAgLS0gc3RhY2tvdmVyZmxvdy5jb20vYS8zNjcyNTAwMwpmb2xkaTEgZiAoaDp0KSA9IGYgaCAuIGZvbGRpMSBmIC4gdW5mb2xkciAoXChhOmI6ciktPiBKdXN0IChmIGEgYiwgcikpICQgdAogICAgICAgICAgICAgICAgICAgICAgIApwczE9MiA6IGZpeCAoKDM6KSAuIGNvbmNhdCAuIHVuZm9sZHIgKFwoeCx1OnVzKS0+IEp1c3QgKFt4fHU9PTBdLCAoeCsyLHVzKSkpIAogICAgICAgICAgICAuICgsKSA1IC4gKFswLDBdICsrKSAKICAgICAgICAgICAgLiBmb2xkaTEgKFwoeDp4cykgeXMgLT4gbGV0IG49ZGl2IChoZWFkIHlzIC0geCkgMiAtIDEgaW4KICAgICAgICAgICAgICAgICAgICAgICAgICB4OnRha2UgbiB4cyArKyB6aXBXaXRoIG1heCB5cyAoZHJvcCBuIHhzKSkKICAgICAgICAgICAgLiBtYXAgKFxwLT4gKHAqcCA6KSAuIHRhaWwgLiBjeWNsZSAkIDEgOiByZXBsaWNhdGUgKHAtMSkgMCkgKQoKbWFpbiA9IHByaW50IC4gdGFrZSAxMCAuIGRyb3AgODAwMDAgJCBwcyAgICAtLSA0MGsgcHMxOjEuODhzIHBzOjEuMjBzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gODBrICAgICA1LjUyICAgICAzLjY4Ci0tIHdoaWNoIGlzIHRvIHNheSwgICAgICAgICAgICAgICAgICAgICAgICAgLS0gICAgICAgIG5eMS42ICAgIG5eMS42Cgpub19jb21wb3MgeCAodTp1cykgPSBbeCB8IHU9PTBdICsrIG5vX2NvbXBvcyAoeCsyKSB1cwpmb2xkaSBmIChoOnQpID0gZiBoIC4gZm9sZGkgZiAuIHBhaXJzIGYgJCB0CnBhaXJzIGYgKGE6YjpyKSA9IGYgYSBiIDogcGFpcnMgZiByCm1qb2luICh4OnhzKSB5cyA9IHggOiBhZnRlciAoZGl2IChoZWFkIHlzIC0geCkgMiAtIDEpIHhzICh6aXBXaXRoIG1heCB5cykgCmFmdGVyIG4geHMgayB8IG4+MCA9IGhlYWQgeHMgOiBhZnRlciAobi0xKSAodGFpbCB4cykgayAgCiAgICAgICAgICAgICB8IG90aGVyd2lzZSA9IGsgeHMgICAgICAgICAgICAgICAgICAgICAgICAgCm11bHRzIHAgPSAocCpwIDopIC4gdGFpbCAuIGN5Y2xlICQgMSA6IHJlcGxpY2F0ZSAocC0xKSAwCnBzID0gMiA6IG9wcyB3aGVyZQogICAgICAgICBvcHMgPSAzOjU6Nzoobm9fY29tcG9zIDkgLiBmb2xkaSBtam9pbiAuIG1hcCBtdWx0cykgb3BzIA==