引入
如果我们想要求出小于 n
的所有素数,一个很自然的想法就是从 1 到 n
进行遍历,然后对素数进行记录,但这样的话时间复杂度为 \(O(n^{\frac{3}{2}})\) ,当 n
足够大的时候这个算法是较慢的,有没有更高效的算法呢?
接下来我们介绍最常见的两种素数筛,以 Leetcode 模版题为例:计数质数
埃氏筛
埃氏筛也叫埃拉托斯特尼筛法,考虑任意素数 x
,则
x
的所有倍数都是合数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public: int countPrimes(int n) { bool* notPrime = new bool[n](); int res = 0; for (int i = 2; i < n; i++) { if (!notPrime[i]) { res++; for (long long k = (long long)i * i; k < n; k += i) { notPrime[k] = true; } } }
return res; } };
|
时间复杂度:\(O(n\ loglogn)\)
如果想了解其证明,读者可以自行去 OI Wiki
上看。
尽管埃氏筛法已经有较高的效率,但其仍然无法达到线性时间复杂度,因为有些数存在重复筛除的情况,例如
12,其会被 2,3 分别筛除一次,有没有办法可以避免重复筛除呢?
欧式筛(线性筛)
欧式筛,即 Euler
筛法,其避免了上述的重复筛而造成的时间浪费,真正意义上实现了线性时间复杂度。对于特别大的数据量(\(n > 10^8\))时适用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public: int countPrimes(int n) { if (n < 2) return 0; int* primeNum = new int[(int)(1.5 * n / log(n)) + 1]; bool* notPrime = new bool[n](); int res = 0; for (int i = 2; i < n; i++) { if (!notPrime[i]) { primeNum[res++] = i; } for (int j = 0; j < res && i * primeNum[j] < n; j++) { notPrime[i * primeNum[j]] = true; if (i % primeNum[j] == 0) break; } }
return res; } };
|
时间复杂度:\(O(n)\)
注意到,欧式筛中被筛除的合数都是被当前记录的最小素数筛除的,所以我们我们也可以同时得到每个数的最小质因数。
案例
HDU -
6954
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <iostream> #include <cmath>
#define MAX_NUM 10000005
using i64 = long long;
bool notPrime[MAX_NUM]; i64 ans[MAX_NUM]; int primeNum[MAX_NUM]; int cnt = 0;
int main() {
std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
for (int i = 2; i < MAX_NUM; i++) { if (!notPrime[i]) { ans[i] = ans[i - 1] + 2ll * i; primeNum[cnt++] = i; } else { ans[i] = ans[i - 1] + i; } for (int j = 0; j < cnt && (i64)i * primeNum[j] < MAX_NUM; j++) { notPrime[i * primeNum[j]] = true; if (i % primeNum[j] == 0) break; } }
int numTest; std::cin >> numTest; int n; while (numTest--) { std::cin >> n; std::cout << ans[n] - 4 << '\n'; }
return 0; }
|