logo标签列表

为什么埃拉托色尼筛法比简单的“愚蠢”算法更高效？

algorithmperformancebig-o
18
如果您需要从1到N生成素数，则“愚蠢”的方法是迭代所有2到N的数字，并检查是否可以被迄今为止找到的小于该数字平方根的任何质数整除。
在我看来，埃拉托斯特尼筛法也是这样做的，只不过相反-当它找到一个质数N时，它标记所有N的倍数的数字。
但是，无论您在找到N时是否标记X，或者您是否检查X是否可以被N整除，基本复杂度（big-O）都保持不变。你仍然对每个数字-质数对执行一个常量时间操作。实际上，愚蠢的算法在找到质数后立即停止，但埃拉托斯特尼筛法对每个可被其除尽的质数都标记每个数字多次。对于每个数字，这至少是两倍的操作次数，除了质数以外。
我在这里有什么误解吗？
8个回答
19
在试除法算法中，确认一个数字 n 是否为质数所需的最大工作量是测试能否被小于约 sqrt(n) 的质数整除。
当 n 是质数或两个大小接近的质数（包括质数的平方）乘积时，会遇到最坏情况。如果 n 有两个以上的质因数或两个大小差异很大的质因数，则其中至少一个比 sqrt(n) 小得多，因此即使需要为所有这些数字累计所需的工作（对于足够大的 N，它们占据了所有数字的绝大部分），这些工作量也相对较小，我将忽略这些，并假设复合数可以在不进行任何工作的情况下确定（两个大小接近的质数的乘积数量很少，因此虽然它们每个的成本与同样大小的质数一样，但总体上那只是极少量的工作）。
那么，测试小于 N 的质数需要多少工作？
根据素数定理，素数 <= n 的数量（对于足够大的 n）约为 n/log n（是 n/log n + lower order terms）。反过来，这意味着第 k 个质数（对于不太小的 k）约为 k*log k（+ lower order terms）。因此，测试第k个质数需要通过试除以约为2*sqrt(k/log k)个质数的平方根pi(sqrt(p_k))，将它们全部相加（对于k <= pi(N) ~ N/log N），总共需要大约4/3*N^(3/2)/(log N)^2次试除。因此，如果我们忽略掉合数，那么使用试除法（只使用质数）寻找前N个质数的时间复杂度是Omega(N^1.5 / (log N)^2)。更详细的分析表明，考虑了合数后时间复杂度为Theta(N^1.5 / (log N)^2)。使用轮筛法可以减小常数因子，但不会改变时间复杂度。
另一方面，在筛法中，每个合数都会被标记为至少一个质数的倍数。取决于从2*p还是p*p开始标记，一个合数则会被标记多次，其数量等于其所拥有的不同素因子的数量或者不超过sqrt(n)的不同素因子的数量。由于任何数字至多只有一个大于sqrt(n)的质因子，这两种情况的差异不会对时间复杂度产生影响，但是有很多数字只有两个质因子（或者三个质因子其中一个大于sqrt(n)），因此这会在运行时间上产生明显的差异。无论如何，一个数n > 0只有少量不同的质因子，一个简单的估计表明，不同质因子的数量受到lg n（以2为底的对数）的限制，因此筛法最多需要进行N*lg N次标记。

通过计算每个素数的倍数被划掉的次数而不是每个合数被划掉的次数，就像 IVlad 已经做的那样，我们很容易发现划掉操作的次数实际上是 Theta(N*log log N)。再次强调使用筛选法并不改变复杂度但可以减少常数因子。然而，在这里它比试除法影响更大，所以至少应该跳过偶数（除了减少工作量外，还可以减小存储空间，从而提高缓存局部性）。

因此，即使不考虑除法比加法和乘法更昂贵的事实，我们也可以看出筛法所需的操作次数要比试除法少得多（如果限制值不太小的话）。

总结：
试除法通过除以素数完成无用的计算，筛选法则通过反复划掉合数完成无用的计算。素数相对较少，但合数很多，因此人们可能会认为试除法浪费的工作会更少。
但是：合数只有很少的不同素因子，而在sqrt(p)以下有许多素数。

3
只为这个概要，你获得了被接受的答案！ - Vilx-
同时通过乘法，您也可以摆脱缓慢的除法。 - phuclv
11
在朴素的方法中，对于每个检查素性的数字，您需要执行O(sqrt(num))次操作。这是O(n*sqrt(n))总次数。
在筛法中，对于从1到n的每个未标记数字，在标记2的倍数时需要执行n / 2次操作，在标记3倍数时需要执行n / 3次操作，在标记5倍数时需要执行n / 5次操作等。这是n*(1/2 + 1/3 + 1/5 + 1/7 + ...)，其时间复杂度为O(n log log n)。请参见此处有关该结果的信息。
因此，渐近复杂度并不相同，就像您所说的那样。即使是朴素筛法也会比朴素的素数生成方法快得多。优化版本的筛法可以更快，但大O记法保持不变。
两种方法并不相同，正如您所说。对于每个数字，在朴素的素数生成算法中，您将通过相同的质数2, 3, 5, 7, ...检查可除性。随着进展，您将检查相同系列的数字（并且随着接近n，您会继续检查更多的数字）。对于筛法，当您接近n时，您将检查越来越少。首先，您以2的增量进行检查，然后是3，5等。这将更快地达到n并停止检查。
不，它不是 O(sqrt(num))，因为我只检查到目前为止找到的质数。请仔细阅读。 - Vilx-
@Vilx - 对于每个数字num，您必须检查它是否可被任何小于等于sqrt(num)的当前质数整除。大约有x / log(x) = O(x)个小于等于x的质数。这意味着您需要为每个数字执行sqrt(num) / log(sqrt(num)) = O(sqrt(num))次操作。想一想。您可能会有一个有利的常数（<1）在那个大O后面，但随着n的增长，它仍然很糟糕。 - IVlad
如果你所说的只是检查到目前为止找到的所有质数（全部质数），那么你的算法实际上是 O(n^2) :）。你需要检查所有已发现的质数，这些质数都小于等于 sqrt(num)。然后像我说的一样，才是 O(n sqrt(n))。 - IVlad
1
我非常确定 O(x/log x) < O(x)。 - Gabe
@Gabe - O(x)是x / log x的一个上界。你知道更紧的上界吗？它不是O(log x)，因为当x趋近于无穷大时，log x / (x / log x)的极限是0。即使它是O(log x)，那仍然比筛法差。如果你有更好的上界，我会编辑进去，但我的观点仍然成立。如果你想的话，你可以把它写成O(x / log x)，但这并没有告诉你更多信息。 - IVlad
2
@IVlad，当比较算法时，将它们的时间复杂度之一舍入到方便的上限，而保持另一个的上限紧密，这是不公平的。朴素方法需要O(nsqrt(n)/log(n))。您的总体观点是正确的，因为O(n log log n)比O(nsqrt(n)/log n)更好，这可以通过绘制(sqrt(n)/log n) / log log n来看出。 - Daniel Stutzbach
6

因为使用筛法时，当运行素数达到N的平方根时，停止标记其倍数。

比如说，你想找出小于一百万的所有素数。

首先设置一个数组

for i = 2 to 1000000
  primetest[i] = true

然后你进行迭代。
for j=2 to 1000         <--- 1000 is the square root of 10000000
  if primetest[j]                                    <--- if j is prime
    ---mark all multiples of j (except j itself) as "not a prime"
    for k = j^2 to 1000000 step j
      primetest[k] = false

你不需要在1000之后检查j，因为j * j将超过一百万。
而你从j * j开始（你不必标记小于j^2的j的倍数，因为它们已经被先前找到的较小质数的倍数标记了）
因此，最终您会循环1000次，并且if部分仅适用于那些是质数的j。
第二个原因是，使用筛法，您只进行乘法运算，而不是除法。如果你聪明地做，你甚至只需要进行加法运算，而无需进行乘法运算。
而且除法比加法具有更大的复杂度。通常的除法方式具有O(n^2)复杂度，而加法具有O(n)复杂度。
嗯？这在测试N是否为质数时很有用，但不适用于生成小于N的所有质数。埃拉托斯特尼筛法主要是一个质数生成器，而不是一个质数测试器。 - Vatine
@Vatine - 不，它对筛法也适用。你只需要标记小于等于 sqrt(n) 的质数的倍数。 - IVlad
5
4

第一个区别是除法比加法昂贵得多。即使每个数字被“标记”多次，与“愚蠢”算法所需的大量除法相比，这都是微不足道的。

3
与此无关，无论是除法还是加法都在常数时间内完成（假设使用定宽整数）。 - IVlad
2
@ypercube - 我是说假设固定宽度的整数。在进行大O分析时，我们可以对事物施加常数上限，这样就不会有任何问题了。因此，在这些情况下，它是一个常数。 - IVlad
3
啊，现在我明白你的意思了。问题是“n”也是我所限制的数字之一，因此通过限制这些数字，我也在隐含地限制“n”。 - IVlad
2
如果你要对大于2^64的数字进行筛法，那么祝你好运。 - Nick Johnson
1
@Todd：在当前的英特尔/AMD CPU上，整数除法比加法慢大约25倍。请参见http://agner.org/optimize/以获取指令延迟和吞吐量信息。在英特尔Haswell的最坏情况下，`div`（无符号）128b / 64b-> 64b的吞吐量可能慢到每74个周期一次（延迟高达96个周期）。标量int add（64b + 64b-> 64b）的吞吐量为每个时钟周期4个，延迟为1个周期。div r32（64b / 32b-> 32b）要好得多：每9到11个周期一个，延迟为22到29c。但是，如果筛选器大于缓存，则您可能仍然是正确的，因为缓存未命中的成本超过100c。 - Peter Cordes
显示剩余14条评论
0
一个“天真”的埃拉托斯特尼筛法会多次标记非质数。 但是，如果您将数字放在链接列表上并删除它们的倍数（您仍然需要遍历列表的其余部分），那么在找到质数后剩下的工作总是比找到质数之前要少。
5
在链表中存储数字是一个很糟糕的想法。链表不允许随机访问，这对筛法的性能至关重要。 - IVlad
4
你正在将其与朴素筛法实现进行比较。为什么要使用int（必须存储实际数字）和指针，当你所需要的只是一个单独的位来告诉你该位对应的数字是质数还是合数？如果你使用数组，你只需要一个单独的位来表示每个数字。如果我想要添加一个wheel（@Landei链接中描述的东西），你的解决方案如何扩展？基本上，如果我想从7开始，并忽略2、3和5的倍数。更不用提使用列表的开销了。此外，你的答案暗示着使用链表比“朴素”筛法更好，这是不正确的。 - IVlad
1
@IVlad，另一种表达方式是，适当的S.E.就像无重复信箱排序：我们能够直接将一个数字放入数组中的正确位置，使用数字作为地址。如果每一步实际上删除了数字，那么直接寻址就不再可能了。 - Will Ness
1
@IVlad：实际上，对于筛法的性能来说，随机访问并不是至关重要的。事实上，随机访问会破坏筛法的性能。随机访问RAM通常会破坏性能，因为它会破坏缓存一致性。按顺序访问数组比随机访问快几个数量级。 - Todd Lehman
2
@ToddLehman - 在数据结构中，随机访问指的是能够在常数时间内访问一个条目的能力，这对于高效的筛法是必要的。访问本身是顺序的，因为它在每一步都是可预测的。 - IVlad
显示剩余3条评论
0
1
我有所怀疑。比如说，如果640000000可以被2整除，就没有必要检查其余部分，因此i/log(i)在这里必须是一个宽松的界限。 - zw324
@Ziyao：嗯，非常有见地！我现在有一种直觉，即“愚蠢”算法中的大部分工作必须来自于确认质数是质数。我已根据这个洞察力重写了我的答案。如果您有更好的界限，请建议。 - ninjagecko
0

那时，我在尝试寻找一种高效的方式来找到小于x的素数之和：

于是我决定使用N乘N的方形表格，并开始检查末位数字为[1,3,7,9]的数字

但是埃拉托色尼筛法使它变得更容易了：如何实现？

  1. 假设你想知道N是否为质数

    你开始找因式分解。所以当你用最高的因子商除N时，你会意识到N被分解了。

    所以，你取一个数字：int(sqrt(N)) = K(假设)将N除以它，你会得到与K相同且接近的数字

  2. 现在假设你用u<K除以N，但如果“U”不是质数，而U的一个质因子是V(质数)，那么显然会小于U(V<U)，并且V也会除以N 那么

    为什么不通过只用小于K=int(sqrt(N))的质数来除以'N'并检查N是否为质数呢？ 循环执行的次数= π(√n) 这就是Eratosthenes的杰出想法开始形成并开始给你这一切背后的直觉。

  3. 顺便说一句，使用Eratosthenes筛法可以找到小于10的倍数的质数之和。

因为对于给定的列，您只需要检查它们的个位数字[1、3、7、9]以及特定单位数字重复的次数。

作为 Stack Overflow 社区的新成员！如果有任何错误，希望能得到建议。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接