欧拉筛法可以以(Theta(n))的时间，空间复杂度求出(1-n)范围内的所有质数. 其核心思想是每个合数仅会被其最小的质因数筛去一次.
See this website for more details.
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN(1000001);
int n_prime(0);
bool not_prime[MAXN];
int prime[80000];
/*
There are 78498 prime numbers in the interval [1, 1000000].
It's secure to use floor(x / ln(x) * 1.14) as the size of prime array.
See the website given above for details.
*/
int main()
{
not_prime[1] = true;
for (int i = 2; i < MAXN; ++i) {
!not_prime[i] && (prime[n_prime++] = i);
for (int j = 0, t; j < n_prime && (t = i * prime[j]) < MAXN; ++j) {
not_prime[t] = true;
if (!(i % prime[j]))
break;
}
}
return 0;
}对于待求区间内的任意合数(n), 其必定存在一个最小质因数(p). 设(m = n / p), 显然, (m < n), 且(m)的最小质因数大于等于(p). 因此, 在not_prime[n]被赋值为true之前, 不会出现m % prime[j] == 0的情况, 也就不会触发跳出循环的break语句. 所以, 待求区间内的所有合数都一定会被筛除.
设(q)为(n)的质因数, 且(q ne p). 令(k = n / q). 因为(p | n), 且(p < q), 所以当外层循环循环至i = k时, 内层循环一定会在循环至prime[j] == q之前触发i % p == 0而导致中断. 因此, 每个合数仅会被其最小的质因数筛去一次, 也就保证了该算法(Theta(n))的复杂度.
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
