Haskell代码排除号码埃拉托色尼的筛预期

我用下面的Sieve of Eratosthenes实施来到不工作：Haskell代码排除号码埃拉托色尼的筛预期

sieve :: (Integral a) => [a] -> [a] 
sieve [] = [] 
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0] 

primes :: (Integral a) => [a] 
primes = sieve [2..100]

调用primes从gchi打印：

[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]

添加出发的optimization step标记号码p，我结束了以下代码：

sieve :: (Integral a) => [a] -> [a] 
sieve [] = [] 
sieve (p:ps) = p:[x | x <- sieve ps, x > p^2, (rem x p) /= 0] 

primes :: (Integral a) => [a] 
primes = sieve [2..100]

但它产生以下输出：

[2]

我是新来的Haskell所以我有问题要理解为什么加入x > p^2正在产生这样的结果。

您可以通过解释Haskell如何评估表达式来发现我的错误吗？

来源

2015-04-22 higuaro

这不是Eratosthenes的筛子。这是一种[试验分区]形式（http://en.wikipedia.org/wiki/Trial_division），速度很慢。要获得更好的功能筛网，请参阅紧密基于Eratosthenes的[O'Neill筛网]（https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf）。 – dfeuer

我很担心这种实现的缓慢，这就是为什么我要跳过第一个“p^2”数字，但是当我通过答案学习时，它并不是那种方式。感谢您的论文链接。 – higuaro

奥尼尔的实际实施比文中的实施要复杂一点（也好多了）。它在'NumberSieves'包中的[Math.Sieve.ONeill]（https://hackage.haskell.org/package/NumberSieves-0.1.1/docs/Math-Sieve-ONeill.html）中。 – dfeuer

你有

sieve [2..10]

它扩展到

2 : [x1 | x1 <- sieve [3..10], x1 > 4, rem x1 2 /= 0] 
    = 2 : [x1 | x1 <- 3 : [x2 | x2 <- sieve [4..10], 
           x2 > 9, 
           x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以第一x1是3，但3 > 4是False，所以我们移动到下一个：

= 2 : [x1 | x1 <- [x2 | x2 <- sieve [4..10], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0] 

    = 2 : [x1 | x1 <- [x2 | x2 <- 4 : [x3 | x3 <- sieve [5..10], 
              x3 > 16, 
              x3 `rem` 4 /= 0], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以，如果x2是4，x2 > 9是假的，所以我们移动到下一个元素：

= 2 : [x1 | x1 <- [x2 | x2 <- [x3 | x3 <- sieve [5..10], 
             x3 > 16, 
             x3 `rem` 4 /= 0], 
          x2 > 9, 
          x2 `rem` 3 /= 0], 
       x1 > 4, 
       x1 `rem` 2 /= 0]

所以我们已经可以看到，我们所知道的唯一的实际值被返回是2，3被跳过，因为3 > 4是False。 4被跳过，但出于错误的原因，并且5将被跳过，因为5 > 16是False，依此类推。这里的问题是你的条件x > p^2过滤整个列表，但你真的想在列表中跳跃前进。这意味着您实际感兴趣的值将从输出中过滤出来。

来源

2015-04-22 20:22:07 bheklilr

谢谢，真的很好的答案！有没有办法使用这种方法在列表中向前跳跃，还是应该以其他方式来做这件事？ – higuaro

@higuaro在上面dfeuer的评论中提到，你实际上并没有用这种风格实现eratosthenes的筛选，最好尝试一种不同的途径来寻找素数。列表理解不允许你跳到前面，它们按顺序处理每个项目。 – bheklilr

@higuaro，就我所知，唯一的（相当简单的）向前跳的方法是使用[轮]（http://en.wikipedia.org/wiki/Wheel_factorization），这是奥尼尔解释得很多的一种技巧在她的论文中更好。轮子问题似乎是，他们很快就会变大。其他方法的重点是尽可能快地咀嚼复合材料。 – dfeuer

这行代码：

p:[x | x <- sieve ps, x > p^2, (rem x p) /= 0]

说： “采取一切从x sieve ps这样x > p^2和x是不是p整除”。这意味着所有小于或等于p^2的数字都将被丢弃。这显然是不正确的（最小的计数器例子：[2..3]）。

来源

2015-04-22 20:21:55 kraskevich

Haskell代码排除号码埃拉托色尼的筛预期

回答

相关问题