懒惰的素数列表

如何实现Haskell中的素数列表，以便可以懒惰地检索它们？懒惰的素数列表

我是Haskell的新手，希望了解懒惰评估功能的实际应用。

2010-08-29 Mantas Vidutis

Something like http://stackoverflow.com/questions/1764163 /求助解释 - 这 - 块 - 的 - 哈斯克尔代码 - - 输出 - 一个流 - 的 - 即素数？ – kennytm 2010-08-29 20:44:44

考虑http://hackage.haskell.org/package/primes – 2010-08-29 23:17:26

恰恰相反：在Haskell – vpolozov 2010-08-31 18:31:46

下面是一个简短的Haskell功能，从Literate Programs:

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

列举素数显然，这是不埃拉托塞尼的筛（感谢，Landei）。我认为这仍然是一个有启发意义的例子，表明您可以在Haskell中编写非常优雅的短代码，并显示如何选择错误的数据结构会严重影响效率。

来源

2010-08-29 20:53:19 Niki

+17

请仔细阅读并重新考虑您的回答： http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf – Landei 2010-08-30 08:19:37

“错误的数据结构”（即列表）与此无关代码的*极端*低效率（O（n^2），* in'n primes产生的*），这反过来是对每个新发现的素数而不是其* * *上的滤波器过早启动的结果。使用滤镜创建[正确推迟]（http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters），它运行在大约O（n^1.4..1.45）（在生成的'n'素数中），就像任何其他正常的审判分工。 – 2012-02-12 00:44:43

[literate programs]（http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29）的链接被破坏。 – ThreeFx 2018-01-01 21:37:16

有许多解决方案可以在haskell wiki中正确生成素数序列。第一，最简单的是Postponed Turner sieve：^{（旧版本... NB）}

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

来源

2010-08-29 20:53:50 sleepynate

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

来源

2010-08-30 08:22:00 Landei

非常有趣，我曾经沉迷了一段时间，看到了单线程的简单性，并发现它与我自己实施筛子的经历形成鲜明对比...他们欺骗了！我很沮丧没有注意到它：p – 2010-08-30 15:23:57

的接受了@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整除的所有数字。

来源

2017-05-25 10:48:41 wwwater

懒惰的素数列表

回答

相关问题