読者です 読者をやめる 読者になる 読者になる

割り算を使わない篩

Haskell

割り算は使ってないけど,sieve のやっている比較が試し割に相当している?

(変更)名前を整理

module Prime (primes,primes') where

import Data.List

primes :: [Integer]
primes = concat primes'

primes' :: [[Integer]]
primes' = [2]:[3]:map fst (iterate collect ([5,7],[6*x+y | x<-[2..],y<-[-1,1]]))

collect :: ([Integer],[Integer]) -> ([Integer],[Integer])
collect (ps,qs) = (ps',qs')
  where
    ((_,qs'),pss) = mapAccumL gatherAndSieve (ps,qs) ps
    ps' = concat pss
    gatherAndSieve (xxs@(x:xs),yys) _ = ((xs,yys'),xxs')
      where
        (xxs',zzs) = span (x^2>) yys
        yys' = sieve (map (x*) (xxs++yys)) zzs
        sieve xxs@(x:xs) yys@(y:ys) 
            | x > y     = y : sieve xxs ys
            | otherwise = sieve xs ys