欧拉质数筛
欧拉质数筛是一种时间复杂度为O(n)快速找出1~n之间的质数的算法
核心思想是：每个合数制备他的最小质因子筛一次，从而保证时间复杂度为O(n)
详细算法：
从小到大枚举每个整数 i，如果 is_prime[i] == true，说明它是一个质数，加入质数表。
用所有已知的质数 p 去筛掉 i * p：标记 i * p 为合数（is_prime[i * p] = false）。
一旦 p 是 i 的最小质因子（即 i % p == 0），就停止筛这个 i 后面的合数：因为 i * p1（p1 > p）在后面一定会由更小的因子组合构造出来，重复了。
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
| #include <bits/stdc++.h>
using namespace std;
int n = 10000;
bool is_prime[10000 + 4];
vector<int> primes;
void euler_prime(int n){
fill(is_prime, is_prime + n + 1, true);
is_prime[0] = is_prime[1] = false;
for(int i = 2; i <= n; i ++){
if(is_prime[i] == true)
primes.push_back(i);
for(int p : primes){
if(i * p > n)
break;
is_prime[i * p] = false;
if(i % p == 0)
break;
}
}
}
int main(){
euler_prime(n);
for (int i = 0; i < primes.size(); ++i)
cout << primes[i] << " ";
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def euler_sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0:
break
return primes
n = 10000
primes = euler_sieve(n)
print(" ".join(map(str, primes)))
|
