APL style

APL style.hs

ps = concat $ scanl (\a b-> dropWhile (<= last a) b) [2]
            $ map (\(x:xs)-> x:takeWhile (< x*x) xs) 
            $ iterate (\(x:xs)-> minus xs [x*x, x*x+2*x..]) 
            $ [3,5..]

ps = concat $ scanl (\a b-> dropWhile (<= last a) b) [2]
            $ map (\(x:xs)-> x:takeWhile (< x*x) xs) 
            $ iterate (\(x:xs)-> let(a,b)=span(<x*x)xs in (x:a,minus b [x*x, x*x+2*x..])) 
                   -- (\(x:xs)-> span (< x*x) xs |> (x:) *** (`minus`  [x*x, x*x+2*x..])) 
            $ [3,5..]
     ......


mapM_ (print.take 30) $ take 20 $ scanl1 minus $ scanl1 (zipWith(+)) $ repeat [2..] 


-- zipWith ($) (map (flip (!!)) [0..]) --
map (head . head) $ iterate (map tail . tail)                 -- _________
    $ scanl1 minus $ scanl1 (zipWith(+)) $ repeat [2..]       -- APL style

-- 1k: 0.34sec   1.5k: 0.73sec   n^1.88


Prelude Saga Data.List> mapM_ (print . take 10) $ take 7 
                          $ scanl1 (zipWith(+) . id  ) $ repeat [1..]
[1, 2, 3, 4, 5, 6, 7, 8, 9,10]
[2, 4, 6, 8,10,12,14,16,18,20]
[3, 6, 9,12,15,18,21,24,27,30]
[4, 8,12,16,20,24,28,32,36,40]
[5,10,15,20,25,30,35,40,45,50]
[6,12,18,24,30,36,42,48,54,60]
[7,14,21,28,35,42,49,56,63,70]

Prelude Saga Data.List> mapM_ (print . take 10) $ take 7 
                          $ scanl1 (zipWith(+) . tail) $ tails  [1..]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
[ 4, 6, 8,10,12,14,16,18,20,22]
[ 9,12,15,18,21,24,27,30,33,36]
[16,20,24,28,32,36,40,44,48,52]
[25,30,35,40,45,50,55,60,65,70]
[36,42,48,54,60,66,72,78,84,90]
[49,56,63,70,77,84,91,98,105,112]

Prelude Saga Data.List> mapM_ (print . take 10) $ take 7 $
  unfoldr (\(a:b:r)-> case span (< head b) a of (h,t)-> Just (h, minus t b:r))
                          $ scanl1 (zipWith(+) . tail) $ tails  [1..]
[1,2,3]
[5,7]
[11,13]
[17,19,23]
[29,31]
[37,41,43,47]
[53,59,61]

Prelude Saga Data.List> (!! 100) $ concat $ unfoldr (\(a:b:r)->     -- 1,2,3,5,7,11,...
  case span (< head b) a of (h,t) ->  Just (h, minus t b:r)) 
    $ scanl1 (zipWith(+) . tail) $ tails  [1..]
541

-- 10k: 0.69sec   15k: 1.40sec   20k: 2.24sec    n^1.74   n^1.63


---- now thread 'primes' through...... 





                                                                    -- [x | x<-xs, rem x p > 0]
primes = map head $ iterate (\(p:xs)-> filter ((> 0).(`rem` p)) xs) 
                      [2..]
-- _________________________________________________________________
primes = unfoldr (\(p:xs)->  Just (p,  filter ((> 0).(`rem` p)) xs))
                      [2..]

  -- 1k: 1.01s   1.2k: 1.46s
  --        n^2.02
-- _________________________________________________________________
primes = (2:) . concat 
       $ unfoldr (\(xs,p:ps)-> case span (< p*p) xs of (h,t) ->     -- [x | x<- t, rem x p > 0]
                             Just (h, (filter ((> 0).(`rem` p)) t, ps)))
                     ([3..], primes)

  -- 10k: 1.24s   12k: 1.58s
  --         n^1.33
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


primes = (2:) . concat $ unfoldr (\(xs,p:ps)-> span (< p*p) >>> second 
                         (filter ((> 0).(`rem` p)) >>> flip (,) ps) >>> Just $ xs)
                     ([3..], primes)


--
primes = _Y $ (2:) . concat . unfoldr (\(xs,p:ps)-> case span (< p*p) xs of (h,t) -> 
                             Just (h, (filter ((> 0).(`rem` p)) t, ps)))
                   . ((,) [3..])

  -- 10k: 1.26s   12k: 1.60s    n^1.31 ..... BUT that's in GHCi, interpreted...

primes = (2:) . _Y $ (3:) . concat . unfoldr (\(xs,p:ps)-> case span (< p*p) xs of (h,t) ->
                             Just (h, (filter ((> 0).(`rem` p)) t, ps)))
                   . ((,) [5,7..])

-- 10k: 1.09s   15k: 1.88s   20k: 2.86s    n^1.34    n^1.46








def eratosthenes(n):
    multiples = []
    for i in xrange(2, n+1):
        if i not in multiples:
            print i
            multiples.extend(xrange(i*i, n+1, i))

mapAccumL .....