埃氏筛及扩展质因数筛——埃拉托斯特尼筛法变种

  质数筛

这段代码用 “埃拉托斯特尼筛法” 找 2 到 N 之间的所有素数，逻辑很直接：

 

1. 先假设所有数都是素数（用vis数组标记，初始全为true）；
2. 排除 0 和 1（它们不是素数，标记为false）；
3. 从 2 开始，对每个没被排除的数 i（说明 i 是素数），把它的所有倍数（从 i×i 开始）都标记为非素数（因为素数的倍数一定不是素数）；
4. 最后把所有没被标记为非素数的数（即素数）收集到prime数组里，统计个数。

 

这样就能高效找出所有素数。

查看代码

const int N = 2e5 + 5;
int prime[N];//存储素数
bool vis[N];//埃拉托斯特尼筛法(质数筛)
void sieve(){memset(vis, true, sizeof(vis));vis[0] = vis[1] = false;for(int i = 2; i * i <= N; ++i){if(vis[i]){for(int j = i * i; j <= N; j += i){vis[j] = false;}}}int cnt = 0;for(int i = 2; i <= N; ++i){if(vis[i]) prime[++cnt] = i;}return ;
}

---

质因数筛

这段代码的作用是找出 1到N 之间每个数的所有质因数，并把每个数的质因数存到fac数组里（比如fac[6]会存[2,3]，因为 2 和 3 是 6 的质因数）。

 

逻辑很简单：

 

• 从 2 开始逐个检查数字i，如果fac[i]是空的，说明i是素数（没被更小的数标记过）。
• 对这个素数i，把它的所有倍数（从i本身开始，比如i=2时，倍数是 2、4、6、8…）的质因数列表里都加上i（因为i是素数，它的倍数一定包含i作为质因数）。

 

这样最后fac[j]里就有j的所有质因数了。

查看代码

const int N = 2e5;
vector<vector<int>> fac(N);void sieve(){for(int i = 2; i <= N; ++i){if(!fac[i].empty()) continue;for(int j = i; j <= N; j += i){fac[j].emplace_back(i);}}
}