algorithm - 为什么埃拉托色尼筛法比简单的 "dumb"算法更有效？

Question

如果您需要生成从 1 到 N 的素数，“愚蠢”的方法是遍历从 2 到 N 的所有数字，并检查这些数字是否可以被目前找到的任何素数整除，即小于相关数字的平方根。

在我看来，Eratosthenes 筛法的作用相同，只是反过来 - 当它找到素数 N 时，它会标记出所有是 N 的倍数的数字。

但是无论是在找到 N 时标记 X，还是检查 X 是否可以被 N 整除，基本的复杂性，大 O 都保持不变。您仍然对每个素数对执行一个恒定时间操作。事实上，愚蠢的算法一找到素数就会中断，但是埃拉托色尼筛法会多次标记每个数字 - 每个素数都可以被它整除一次。对于除素数以外的每个数字，这至少是两倍的运算。

我是不是误会了什么？

Answer 1

在试分算法中，判断一个数是否可​​能需要做的最多的工作n是素数，正在测试素数的整除性直到大约 sqrt(n) .

最坏的情况发生在 n 时。是一个质数或两个大小几乎相同的质数(包括质数的平方)的乘积。如果n有两个以上的质因数，或两个大小非常不同的质因数，至少其中一个比sqrt(n)小得多，所以即使所有这些数字(占所有数字的绝大多数，直到 N，足够大的 N)所需的累积工作也相对微不足道，我将忽略这一点并使用合数的虚构无需做任何工作即可确定(两个近似相等的素数的乘积数量很少，因此尽管它们单独的成本与大小相似的素数一样多，但总的来说工作量可以忽略不计)。

那么，对直到 N 的素数的测试需要做多少工作？拿？

根据素数定理，素数的个数<= n是(对于 n 足够大)，关于 n/log n (它是 n/log n + lower order terms )。相反，这意味着第 k 个素数(对于 k 来说不是太小)大约是 k*log k (+ 低阶项)。

因此，测试第 k 个素数需要用 pi(sqrt(p_k)) 进行试验除法, 大约 2*sqrt(k/log k) , 素数。总结 k <= pi(N) ~ N/log N产量大约为 4/3*N^(3/2)/(log N)^2总分。因此，通过忽略组合，我们发现找到最多为 N 的素数。通过试验除法(仅使用素数)，是 Omega(N^1.5 / (log N)^2) .对复合 Material 的进一步分析表明它是 Theta(N^1.5 / (log N)^2) .使用轮子可以减少常数因子，但不会改变复杂性。

另一方面，在筛子中，每个组合都作为至少一个素数的倍数被划掉。取决于你是否在 2*p 处开始划线或在 p*p , 复合 Material 被划掉的次数与它具有不同的素因子或不同的素因子一样多<= sqrt(n) .因为任何数字至多有一个质因数超过sqrt(n) ，差异不是很大，它对复杂性没有影响，但有很多数字只有两个素数(或三个，其中一个大于 sqrt(n) )，因此它在运行时间上有显着差异。无论如何，一个数字 n > 0只有几个不同的素因子，一个简单的估计表明不同的素因子的数量受限于 lg n (以 2 为底的对数)，因此筛网交叉数的上限是 N*lg N .

正如 IVlad 所做的那样，不计算每个合数被划掉的频率，而是计算每个素数的倍数被划掉的次数，很容易发现划掉的次数实际上是 Theta(N*log log N) .同样，使用轮子不会改变复杂性，但会减少常数因子。不过这里比trial划分的影响更大，所以至少应该跳过evens(除了减少工作量，也减少了存储大小，所以提高了cache locality)。

因此，即使忽略除法比加法和乘法更昂贵，我们看到筛法所需的操作次数比试除法所需的操作次数要少得多(如果限制不是太小的话)。

总结:
试验除法通过划分质数来做徒劳的工作，筛子通过重复划掉组合来做徒劳的工作。质数相对较少，但合数很多，因此人们可能会认为试验除法浪费的工作较少。
但是:复合 Material 只有几个不同的素因子，而 sqrt(p) 下面有很多素数.