- 一、埃氏筛
- 1.原理：
- 2.代码
- 二、欧拉筛
- 1.前言
- 2.原理
- 3.代码
- 总结
质数的倍数不是质数。
时间复杂度：
O
(
n
l
o
g
2
2
n
)
O(nlog^2_2n)
O(nlog22n)
埃氏筛的时间复杂度不会证明，可戳别处
int prm[255], prm_cnt;//存放素数的数组、素数个数
bool iscompos[255];//true代表为合数，false代表素数数
void make_prime(int n) {
if (n <= 1)return;
for (int i = 2; i <= n; i++) {
if (iscompos[i] == 0) {
prm[++prm_cnt] = i;
for (int j = i * i; j <= n; j += i) {
iscompos[j] = 1;
}
}
}
return;
}
二、欧拉筛
1.前言
埃氏筛中，例如21会被3、7同时筛去。
我们希望每个合数仅被筛去一次。于是有了欧拉筛。
2.原理每个合数仅被最小质因子/最大因数筛去
时间复杂度：
O
(
n
)
O(n)
O(n)
每个数仅被处理一次故时间复杂度为
O
(
n
)
O(n)
O(n)
//时间复杂度：O(n)
int prm2[maxn], cnt2, tab2[maxn];
void make_prime2(int x) {
if (x <= 1)return;
for (int i = 2; i <= x; i++) {
if (!tab2[i])
prm2[++cnt2] = i;
for (int j = 1; j <= cnt2 && prm2[j] * i < x; j++) { // 枚举素数，筛去倍数
tab2[i * prm2[j]] = 1;
if (!(i % prm2[j])) // 当前数为该素数的倍数，即 prm[j] 为最小质因子
break;
}
}
}
朝花夕拾喵~
总结
一般埃氏筛好像就够用了，但能用欧拉筛还是尽量用欧拉筛吧
