割り算を使わない篩
割り算は使ってないけど,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