ACM-学习记录-素数筛

本文最后更新于:2020年11月21日 晚上

前言

近期发现我NEFU低年级组校赛题目只有模拟+数论,恰恰都是我最不会做的,数论方面反反复复用到的就是素数筛,特在此记录一下,闲来无事自己翻阅当作复习复习,以免被到时候一道题都做不出来菜到巨佬们。

代码

查找2-N的所有素数,如下

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
//线性筛
void init() {
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j]) {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
} else {
// i % pri[j] == 0
// 换言之,i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的,所以 i 乘上其他的质数的结果一定也是
// pri[j] 的倍数 它们都被筛过了,就不需要再筛了,所以这里直接 break
// 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}

数论确实是想杀了我- -


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!