2

欧拉筛比埃拉托色尼筛具有更好的渐近复杂度，并且可以用命令式语言简单地实现。

我想知道是否有任何方法可以用流优雅地实现它。我已经检查了haskell wiki 关于素数的信息，但是这两种实现比该 wiki 中的其他筛子（甚至是试除法！）慢数百倍。

所以我尝试自己写：

{-sieve of Euler-}
primesEU = 2:sieve [3,5 ..] where
    sieve (p:i:xt) = p:(sieve (i:xt) `minus` (lps i)) where
        lps i = map (i*) (takeWhile' (\p->(p<i)&&(mod i p /= 0)) primesEU)

takeWhile'::(t->Bool)->[t]->[t]
takeWhile' p [] = []
takeWhile' p (x:xs) = case (p x) of
    True  -> x:takeWhile' p xs
    False -> [x]

minus::(Ord t) => [t]->[t]->[t]
minus [] _ = []
minus xs [] = xs 
minus xs@(x:xt) ys@(y:yt) 
                      |x<y  = x:(minus xt ys)
                      |x==y = minus xt yt
                      |x>y  = minus xs yt

minus类似于minusin Data.List.Ord。

takeWhile'与 类似takeWhile，但有细微差别：takeWhile删除不满足谓词的第一个元素；takeWhile'会接受的。

lsp i返回 i 的有限乘积流，素数不超过 i 的最小素数。

可悲的是，我的实现运行速度非常慢......而且我找不到罪魁祸首。

无论如何，是否有可能以流处理方式实现高效的欧拉筛？还是该算法具有与流的本质相反的固有特性？

4

1 回答 1

5 
primesEU = 2:sieve [3,5 ..] where
    sieve (p:i:xt) = p:(sieve (i:xt) `minus` (lps i)) where
        lps i = map (i*) (takeWhile' (\p->(p<i)&&(mod i p /= 0)) primesEU)

首先，实现是不正确的，它认为 9 素数。我怀疑你的意思是sieve (i:xt) `minus` lps p那里。

然后，由于筛选后的列表仅包含奇数，您可以限制为tail primesEUin lps，这会产生很小的差异。

那么这里发生了什么？

它的要点（我马上去吃晚饭，回来时会扩展）是每个素数p必须冒泡通过小于[不完全，一些被消除minus的奇数（ ）创建的所有调用前]。那是层，每层都需要一个步骤。>= 3pminus(p-3)/2

因此，除了常数因素和复合因素之外，产生素数<= n成本O(∑ p)，其中总和超过素数不大于n。那就是O(n²/log n)。

让我们按照评估的几个步骤sieve [3,5 .. ]。为简洁起见，我用s k列表sieve [k, k+2 ..]和minus表示(\\)。我使用更正的定义

sieve (k:ks) = k : (sieve ks `minus` lps k)

这不考虑 9 素数。我立即展开倍数列表，这在一定程度上减少了工作量。我们得到

 (:)
 / \
3  (\\)
   /  \
 s 5  [9]

立即，然后可以直接消耗3。之后，minus右子树的顶部需要s 5进行足够的评估以判断它是否为空。

   (\\)
   /  \
 (:)  [9]
 / \
5  (\\)
   /  \
 s 7  [15,25]

这是一步完成的。（然后需要判断是否lps 3为空，后面也一样，但是对于 a 的每个成员lps k，这只是一步，所以我们可以忽略它。）然后minus需要一个比较，将 5 冒泡到顶部，离开

   (:)
   / \
  5  (\\)
     /  \
  (\\)  [9]
  /  \
s 7  [15,25]

现在，在消耗完 5 之后，(:)需要扩展顶部的右孩子

      (\\)
      /  \
   (\\)  [9]
   /  \
 (:)  [15,25]
 / \
7  (\\)
   /  \
 s 9  [21,35,49]

将 7 移至 5 的倍数的比较

     (\\)
     /  \
   (:)  [9]
   / \
  7  (\\)
     /  \
  (\\)  [15,25]
  /  \
s 9  [21,35,49]

还有一个将其提升到超过 3 的倍数

      (:)
      / \
     7  (\\)
        /  \
     (\\)  [9]
     /  \
  (\\)  [15,25]
  /  \
s 9  [21,35,49]

在移动了 7 过去的两个复合列表之后，它已经可以使用了。(:)之后，必须进一步评估此处顶层的右子树以确定下一个素数（如果有的话）。评估必须降低(\\)树中的三个级别，以达到s 9提供下一个候选者的级别。

         (\\)
         /  \
      (\\)  [9]
      /  \
   (\\)  [15,25]
   /  \
 (:)  [21,35,49]
 / \
9  (\\)
   /  \
 s 11 [27]

该候选人必须通过两个minuses 才能最终达到minus消除它的

        (\\)
        /  \
     (\\)  [9]
     /  \
   (:)  [15,25]
   / \
  9  (\\)
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

        (\\)
        /  \
      (:)  [9]
      / \
     9  (\\)
        /  \
     (\\)  [15,25]
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

现在minus罐头第一次完成它的工作，生产

           (\\)
           /  \
        (\\)  []
        /  \
     (\\)  [15,25]
     /  \
  (\\)  [21,35,49]
  /  \
s 11 [27]

（xs `minus` []顶部的 仅在第一个参数被确定为非空后才消除空列表；交换 的前两个方程minus会改变这一点，但所需步骤的差异会很小）。然后评估必须在树中下降四个级别以产生下一个候选者 (11)。该候选人必须被提升到四岁minus以上，直到它到达顶部。在此过程中，从树中删除了一个，因此下一个候选者 (13) 仅在树的下层产生minus四层，而不是五层(不完全是，但也不少。(13-3)/2p(p-3)/2

an 中的最后一个元素lps k总是能被 的最小素因数的平方整除k，而且它们都是奇数，所以至多有

1/2*(n/3² + n/5² + n/7² + n/11² + ...) ~ n/10

到达时可以消除的列表n（少了一些，因为它计算了所有具有平方素数除数的数字，以及那些数次以上的数）。

所以问题是每个素数都是在树的深处产生的，至少p*0.4从顶部开始。这意味着提升p到顶部以使其可消耗至少需要几个p*0.4步骤，给出基本上是二次的整体复杂性，不计算生成倍数列表所需的工作。

然而，实际行为一开始更糟，当计算 100000 和 200000 之间的区域中的素数时，它接近二次行为 - 应该成为极限的二次模对数因子，但我认为我没有耐心等待一两万。

无论如何，是否有可能以流处理方式实现高效的欧拉筛？还是该算法具有与流的本质相反的固有特性？

我无法证明这是不可能的，但我知道没有办法有效地实施它。既不是产生一个素数流，也不是产生一个给定限制的素数列表。

使 Eratosthenes 筛法有效的原因在于，它很容易到达一个素数的下一个倍数（只需在索引中添加p或2*p左右），而无需关心它是否已经作为较小素数的倍数被划掉。避免多次划线所需的工作远比多次划线的工作要多。

于 2012-12-16T17:17:04.530 回答