list 懒惰的质数列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3596502/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Lazy List of Prime Numbers
提问by Mantas Vidutis
How would one implement a list of prime numbers in Haskell so that they could be retrieved lazily?
如何在 Haskell 中实现素数列表，以便可以懒惰地检索它们？
I am new to Haskell, and would like to learn about practical uses of the lazy evaluation functionality.
我是 Haskell 的新手，想了解惰性求值功能的实际用途。
采纳答案by Niki
Here's a short Haskell function that enumerates primes from Literate Programs:
这是一个简短的 Haskell 函数，它从文学程序中枚举素数：
primes :: [Integer]
primes = sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
Apparently, this is notthe Sieve of Eratosthenes (thanks, Landei). I think it's still an instructive example that shows you can write very elegant, short code in Haskell and that shows how the choice of the wrong data structure can badly hurt efficiency.
显然，这不是Eratosthenes 的筛子（谢谢，Landei）。我认为这仍然是一个很有启发性的例子，它表明你可以用 Haskell 编写非常优雅的短代码，并且表明选择错误的数据结构会如何严重影响效率。
回答by Landei
I'd suggest to take one of the implementations from this paper: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
我建议采用本文中的一种实现：http: //www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
回答by sleepynate
There are a number of solutions for lazy generation of prime sequences right in the haskell wiki. The first and simplest is the Postponed Turner sieve: (old revision ... NB)
在haskell wiki 中有许多用于延迟生成素数序列的解决方案。第一个也是最简单的是延迟特纳筛：（旧版本......注意）
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
回答by Daria
The accepted answer from @nikie is not very efficient, is gets relatively slow after some thousands, but the answer of @sleepynate is much better. It took me some time to understand it, therefore here is the same code, but just with variables named more clearly:
来自@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]
The main idea is that the candidates for the next primes already contain no numbers that are divisible by any prime less than the first prime given to the function. So that if you call
主要思想是，下一个素数的候选者已经不包含可以被任何小于给定函数的第一个素数的素数整除的数字。所以如果你打电话
calcNextPrimes (5:ps) [11,13,17..]
the candidate list contains no number, that is divisible by 2or 3, that means that the first non-prime candidate will be 5 * 5, cause 5* 2and 5 * 3and 5 * 4are already eliminated. That allows you to take all candidates, that are smaller than the square of 5 and add them straight away to the primes and sieve the rest to eliminate all numbers divisible by 5.
候选名单中没有数，即整除2或者3，这意味着第一个非主要候选对象将是5 * 5，事业 5* 2和5 * 3和5 * 4已经消除。这使您可以将所有小于 5 的平方的候选者直接添加到素数中，然后筛选其余的以消除所有可被 5 整除的数。
回答by Tianren Li
primes = 2 : [x | x <- [3..], all (\y -> x `mod` y /= 0)
(takeWhile (<= (floor . sqrt $ fromIntegral x)) primes)]
With 2in the list initially, for each integer xgreater than 2, check if for all yin primessuch that y <= sqrt(x), x mod y != 0holds, which means xhas no other factors except 1and itself.
与2在列表中最初，对于每个整数x大于2，检查是否对于所有y在primes使得y <= sqrt(x)，x mod y != 0保持装置，该装置x没有其它的因素，除了1和本身。
