如何在O（n）时间复杂度中实现Eratosthenes的筛分？

Question

[此算法的实现可以找到n时间复杂度最高为O(n*log(log(n))的质数。如何在O(n)时间复杂度中实现它？

Answer 1

您可以在[2, n]时间中执行Eratosthenes筛分以确定在O(n)范围内哪些数字是质数：

• 对于间隔x中的每个数字[2, n]，我们计算x的最小素数。为了实现目的，可以通过保留一个数组-MPF[]-来轻松实现，其中MPF[x]表示x的最小素数。最初，应将每个整数MPF[x]的x设置为零。随着算法的进行，该表将被填充。

• 现在，我们使用一个for循环，并从i = 2迭代到i = n（含）。如果我们遇到一个MPF[i]等于0的数字，那么我们会立即得出结论i是质数，因为它没有最小质数因数。此时，通过将i插入列表将其标记为素数，并将MPF[i]设置为等于i。相反，如果MPF[i]确实等于0，则我们知道i是合成的，其最小素数等于MPF[i]。

• 在每次迭代中，我们检查MPF[i]后，执行以下操作：为小于或等于y_j = i * p_j的每个素数p_j计算数字MPF[i]，并将MPF[y_j]设置为等于到p_j。

这似乎违反直觉---如果我们有两个嵌套循环，为什么运行时O(n)？关键思想是每个值都设置为正好一个，因此运行时间为O(n)。这个website提供了一个C ++实现，我在下面提供了它：

const int N = 10000000;
int lp[N+1];
vector<int> pr;

for (int i=2; i<=N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back (i);
    }
    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
        lp[i * pr[j]] = pr[j];
}

以上实现中的数组lp[]与我在解释中描述的MPF[]相同。另外，pr存储质数列表。

Answer 2

好吧，如果算法为O（n * log（n）），那么通常不更改算法就无法做得更好。