流处理中欧拉的高效筛法

Question

Sieve of euler比Sieve of Eratosthenes具有更好的渐近复杂度，并且可以简单地用命令式语言实现。

我想知道是否有任何方法可以用流优雅地实现它。我已经检查了关于素数的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 的最小素数的素数的乘积的有限流。

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

无论如何，是否有可能以流处理风格实现有效的欧拉筛分？或者该算法具有与流的性质相悖的固有特性？

Answer 1

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由奇数（创建呼叫>= 3）小于p[不大，一些minus被淘汰前]。那是(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 之后，(:)需要扩展top 的右孩子

      (\\)
      /  \
   (\\)  [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直到它达到顶峰。一个minus是从在该过程中的树消除，所以下一个候选（13）只产生四个级别沿树向下，而不是五（(13-3)/2），由此的步骤，使数字p顶端，使得它可以被消耗不完全是(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 之间的区域计算质数时它接近二次行为 - 应该成为极限的二次模对数因子，但我认为我没有耐心等待一两万。

无论如何，是否有可能以流处理风格实现有效的欧拉筛分？或者算法有什么与流的本质相悖的固有特性？

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

是什么让埃拉托色尼的筛有效的是，它是微不足道达到黄金的下一个倍数（只添加p或2*p左右索引），而不关心它是否已经被划掉的小素数的倍数。避免多次交叉所需的工作比多次交叉的工作要多得多。