这种算法的实现可以在O(n*log(log(n))时间复杂度内查找高达n的素数。我们如何在O(n)时间复杂的情况下实现这一目标？
您可以执行埃拉托色尼筛，以确定哪些数字在O(n)时间内[2, n]范围内是素数，如下所示：
-
对于区间
[2, n]中x的每个数，我们计算x的最小素因数。出于实现目的，这可以通过保留一个数组---例如MPF[]---轻松完成，其中MPF[x]表示x的最小素因数。最初，应为每个整数xMPF[x]设置为等于零。随着算法的进展，此表将被填满。 -
现在我们使用 for 循环并从
i = 2迭代到i = n(含)。如果我们遇到一个MPF[i]等于0的数，那么我们立即得出结论，i是素数，因为它没有最小素因数。此时，我们通过将其插入列表中来将i标记为素数，并将MPF[i]设置为等于i。相反，如果MPF[i]不等于0，那么我们知道i是复合的，最小素因数等于MPF[i]。 -
在每次迭代中，在我们检查
MPF[i]后，我们执行以下操作：计算每个素数p_j小于或等于MPF[i]的数y_j = i * p_j，并将MPF[y_j]设置为等于p_j。
这似乎违反直觉---如果我们有两个嵌套循环，为什么运行时O(n)？关键思想是每个值都只设置一个，因此运行时是O(n)。这个网站提供了一个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*log(n))，如果不改变算法，你通常不能做得更好。
复杂度为 O(n*log(n))。但是你可以在时间和资源之间进行交易：通过确保你有一个并行运行的O(log(n))计算节点，就可以在O(n)中做到这一点。
希望我没有做你的功课...