素数惰性列表

下面是一个简短的haskell函数,它枚举 Literate Programs:

primes :: [Integer]
primes = sieve (2 : [3, 5..])
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

显然,这是 不 埃拉托斯特尼的筛子(谢谢,兰迪)。我认为这仍然是一个很有启发性的例子,它表明你可以用haskell编写非常优雅、简短的代码,并说明选择错误的数据结构会严重损害效率。

我建议从本文中选择一个实现: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

在haskell wiki中,有许多解决方案可以延迟生成素数序列。第一个也是最简单的是 Postponed Turner sieve : ^{(旧版本…铌)}

primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
 where 
  sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]  
                                -- or:  filter ((/=0).(`rem`p)) t
                  where (h,~(_:t)) = span (< p*p) xs

来自@nikie的公认答案不是很有效,在几千次之后会变得相对缓慢,但是@sleepynate的答案要好得多。我花了一些时间来理解它,因此这里有相同的代码,但只是用变量命名更清楚:

lazyPrimes :: [Integer]
lazyPrimes = 2: 3: calcNextPrimes (tail lazyPrimes) [5, 7 .. ]
  where
    calcNextPrimes (p:ps) candidates =
      let (smallerSquareP, (_:biggerSquareP)) = span (< p * p) candidates in
      smallerSquareP ++ calcNextPrimes ps [c | c <- biggerSquareP, rem c p /= 0]

其主要思想是,下一个素数的候选数已经不包含任何可被小于给定给函数的第一个素数的任何素数除尽的数字。所以如果你打电话

calcNextPrimes (5:ps) [11,13,17..]

候选列表中没有可被除的数字 2 或 3 这意味着第一个非主要候选人将 5 * 5 ,原因 5* 2 和 5 * 3 和 5 * 4 已经被淘汰了。这样你就可以得到所有小于5的平方的候选数,然后直接把它们加到素数上,然后筛选剩下的数,去掉所有被5整除的数。

primes = 2 : [x | x <- [3..], all (\y -> x `mod` y /= 0) 
                   (takeWhile (<= (floor . sqrt $ fromIntegral x)) primes)]

用 二 在列表中,对于每个整数 x 大于 二 ,检查是否全部 y 在里面 primes 这样 y <= sqrt(x) , x mod y != 0 持有,这意味着 X 除了 一 本身。