当要判断一个数是否为素数的时候，素数筛法有很多，但是他们的核心思想是基本相同的即素数可以和其他数相乘得到合数，筛去合数剩下的就是素数。最近一段时间发现素数筛法并不只是单独的运用在判断素数，而是可以通过简单魔改而得到其他功能。
基本素数筛法
用筛法求素数的基本思想是：把从 $2$ 到 $N$ 的一组正整数从小到大按顺序排列。从中依次标记 $2$ 的倍数、$3$ 的倍数、$5$ 的倍数，直到根号 $N$ 的倍数为止，剩余的即为所有素数。素数筛法最常用的是两种，一种是 $O(n\log n)$ 时间复杂度的埃拉托斯特尼筛法，一种是 $O(n)$ 的欧拉筛法。在 $N\leq 1e7$ 范围内可以使用埃式筛和欧拉筛，而对于更大范围的数的情况下要考虑使用素数筛以外的方法去解决问题。
埃拉托斯特尼筛法
埃式筛就是上面核心思想的应用，他用素数乘上其他数得到合数来筛掉之后的很多合数，向后遍历时遇见没有被之前筛掉的数就是素数，循环往复。
bool isPrime[N];
vector<int> prime;
void Eratosthenes() {
for (int i = 0; i <= N; i++)
isPrime[i] = true;
isPrime[0] = isPrime[1] = 0;
// only run to the sqrt(N)
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
prime.push_back(i);
// prevent overflow
if ((long long)i * i <= N)
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
}
欧拉筛法
欧拉筛不太一样的地方是它不会重复的标记合数，那么就使得它的时间复杂度为 $O(n)$。代码结构和埃式筛基本相同，其中有一行保证了它的线性复杂度。
bool isComp[N];
vector<int> prime;
void Euler() {
for (int i = 2; i < N; i++) {
if (!isComp[i])
prime.push_back(i);
for (int j = 0; j < prime.size() && i * prime[j] < N; j++) {
isComp[i * prime[j]] = true;
// avoid repeating operations
if (i % prime[j] == false) {
break;
}
}
}
}
筛法的其他应用
最近通过一些题目发现这个素数筛是可以进行魔改的，功能也能得到扩展。算法要触类旁通，通过理解其中的原理，去把他们应用在不同的场景才是最好的。比赛中的题目真正的模板题也不是很多，所以更加需要对这些数据结构或者算法进行改动。
求取质因数个数
质因数个数在筛素数的时候就可以求出来了，有一道变种 Nim 博弈的题目 https://acm.hdu.edu.cn/showproblem.php?pid=7061 需要得到某个数的质因子个数，可以知道的是质数的质因子数是 1，而两个数相乘之后质因数的个数是他们质因数个数之和。
void Prime() {
for (int i = 2; i < N; i++) {
if (!isComp[i]) {
prime.push_back(i);
cnt[i] = 1;
}
// The number of prime factors after multiplying two numbers is the sum
// of the number of their prime factors.
for (int j = 0; j < prime.size() && i * prime[j] < N; j++) {
isComp[i * prime[j]] = 1;
if (i % prime[j] == 0) {
cnt[i * prime[j]] = cnt[i] + cnt[prime[j]];
break;
}
cnt[i * prime[j]] = cnt[i] + 1;
}
}
}
解决除数问题
这个题 https://codeforces.com/contest/1475/problem/G 利用了埃式筛的方法去更新 DP 数组中能够整除当前数的个数。一个数可以被 $n$ 个数整除，那么这些除数同样可以去整除这个数的倍数。这跟上面的求质因子个数有异曲同工之处，只要找到包含在因数或倍数之间的关系，就能够通过筛的方法来降低更新答案的复杂度到 $O(n)$ 或 $O(n\log n)$。