一、试除法求素数
（通常会超时）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool isPrime(int n){
for(int i = 2; i <= sqrt(n); i++){
if(n%i==0)
return false;
}
return true;
}
int countPrimes(int n) {
if(n == 0 || n == 1)
return 0;
int cnt = 0;
for(int i = 2; i < n; i++){
if(isPrime(i))
cnt++;
}
return cnt;
}
|
二、埃氏筛（厄拉多塞筛法）
可以计算n<=10^7的数
1
2
3
4
5
6
7
8
9
10
11
12
13
| int countPrimes(int n) {
vector<bool>vis(n,false);
int cnt = 0;
for(int i = 2; i < n; i++){
if(!vis[i]){
cnt++;
for(int j = i+i; j < n; j += i){
vis[j] = true;
}
}
}
return cnt;
}
|
预处理素数筛：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const mx = 1000
var primes = []int{0}
func init() {
isPrime := [mx]bool{}
for i := 2; i < mx; i++ {
if !isPrime[i] {
primes = append(primes, i)
for j := i * i; j < mx; j += i {
isPrime[j] = true
}
}
}
fmt.Println(primes)
}
|
三、线性筛（欧拉筛）
在数据量比较大的时候，线性筛的效率更高。
算法思想：每个合数只被划掉一次，因此划去 每个数x 乘上<=x的最小质因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| const mx = 1e6 + 1
var primes = make([]int, 0)
func init() {
isPrime := [mx]bool{}
for i := 2; i < mx; i++ {
if !isPrime[i] {
primes = append(primes, i)
}
for _, p := range primes {
if i*p >= mx {
break
}
isPrime[i*p] = true
if i%p == 0 {
break
}
}
}
}
|
