haskell - 使用 Eratosthenes 筛法寻找素数不起作用 - Haskell

Question

这是我尝试使用的代码：这应该生成最多 100 的所有素数

sieve_primes = [x | x<-[2..100], y<-[2..50], z <-[2..25], (x*z) `mod` y /= 0]

Answer 1

编码

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1

计算所有因素只是为了计算它们。您不需要计算它们：一旦找到第二个因素，您就可以停止搜索而无需检查其他因素。

因此，在检查其长度之前，要么替换length ... == 1为自定义谓词，要么替换take 2列表理解中的元素。

Answer 2

你想到的可能是

Prelude> [x| x<-[2..100], not $ elem x [y*z| y<-[2..50], z<-[2..25]]]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

这是非常缓慢的。至少我们可以重新排列碎片，

Prelude> [x| let sieve=[y*z| y<-[2..50], z<-[2..25]], 
             x<-[2..100], not $ elem x sieve]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

这仍然非常慢，对于任何远高于 1000 的数字（您将使用 500 和 250）。再说一次，为什么有 25 (250) 个限制？您的代码遵循

primes = [x| x<-[2..], not $ elem x 
                       [y*z| y<-[2..x`div`2], z<-[2..min y (x`div`y)]]]

想法，即y*z = 2*y .. min (y*y) x，因此使用已知的上限 ( x <= n) 它应该是

primesTo n = [x| let sieve=[y*z| y<-[2..n`div`2], z<-[2..min y (n`div`y)]],
                 x<-[2..n], not $ elem x sieve]

（顺便说一下max (min y (n/y)) {y=2..n/2} = sqrt n，所以我们可以使用 10 而不是 25，（对于 1000，我们可以使用 31 而不是 250））。

现在 1000 不是问题，仅高于 ~ 10,000 我们再次开始看到它很慢（仍然），以n ^2.05..2.10 经验增长顺序运行（在 GHCi 中快速测试解释代码n = 5000, 10000, 15000） .

---

至于您的第二个（现已删除）功能，可以重写它，逐步提高其速度，如

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1
          = take 1 [x | x<-[2..n], n `mod` x == 0] == [n]
          = [x | x<- takeWhile ((<=n).(^2)) [2..n], n `mod` x == 0] == []
          = and [n `mod` x > 0 | x<- takeWhile ((<=n).(^2)) (2:[3,5..n])]

现在，编译后，它可以在十分之几秒内获得前 10,000 个素数。