欧拉筛求质数

欧拉筛是一种优秀的筛质数方法。

埃氏筛

一般的筛法,时间复杂度 $O(n \times log (log n))$ 。

1
2
3
4
5
6
7
8
9
10
11
12
void sieve(int n) {
cnt = 0;
memset(flag, 0, sizeof(flag));
for (int i = 2; i <= sqrt(n); i++) {
if (!flag[i]) {
prime[cnt++] = i;
for (int j = i * i; j <= n; j += i) {
flag[j] = true;
}
}
}
}

欧拉筛

欧拉筛可以保证每个数只会被筛到一次,故时间复杂度为 $O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
void sieve(int n) {
cnt = 0;
memset(flag, 0, sizeof(flag));
for (int i = 2; i <= n; i++) {
if (!flag[i])
prime[cnt++] = i;
for (int j = 0; i * prime[j] <= n; j++) {
flag[i * prime[j]] = true;
if (i % prime[j] == 0)
break;
}
}
}

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×