如何在 O(n) 时间复杂度下实现 Eratosthenes 筛法？

Question

在 O(n*log(log(n)) 时间复杂度内实现了查找最大 n 素数的算法。我们如何在 O(n) 时间复杂度内实现它？

Answer 1

好吧，如果算法是 O(n*log(n)) 的话，你通常不能在不改变算法的情况下做得更好。

复杂度为O(n*log(n))。但是您可以在时间和资源之间进行交易：通过确保您有 O(log(n)) 个并行计算节点运行，可以在 O(n).

中完成

希望我没有做你的功课...

Answer 2

您可以执行埃拉托色尼筛法以确定 [2, n] 范围内的哪些数字在 O(n) 时间内是质数，如下所示：

对于区间[2, n]中的每个数字x，我们计算x的最小质因数。出于实施目的，这可以很容易地通过保留一个数组来完成——比如 MPF[]——其中 MPF[x] 表示 x 的最小质因数。最初，您应该将每个整数 x 的 MPF[x] 设置为零。随着算法的进行，这个 table 将被填充。
现在我们使用 for 循环并从 i = 2 迭代到 i = n（包括）。如果我们遇到 MPF[i] 等于 0 的数字，那么我们会立即得出结论 i 是素数，因为它没有最小素数因子。此时，我们通过将 i 插入到列表中来将其标记为质数，并将 MPF[i] 设置为 i。相反，如果 MPF[i] 不等于 0，那么我们知道 i 是最小质因数等于 MPF[i] 的复合。
在每次迭代中，在我们检查了 MPF[i] 之后，我们执行以下操作：为每个小于或等于 p_j 的素数计算数字 y_j = i * 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 存储素数列表。

如何在 O(n) 时间复杂度下实现 Eratosthenes 筛法？

How can sieve of Eratosthenes be implemented in O(n) time complexity?

algorithm

primes

time-complexity

sieve-of-eratosthenes