Euler 筛法（欧拉筛法）

本文主要是介绍Euler 筛法（欧拉筛法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

筛法 - OI Wiki

埃氏筛法很好理解，素数的倍数都是合数，做标记不筛即可。

但是2和3都能筛到6，12,18,等，会重复标记。

欧拉筛理解：

筛选 n 以内的素数，存入vector<int>pri 中。

not_prime标记合数。

# 埃氏筛是给 质数 乘以 每个 i，得出所有倍数。

# 这里给 每个 i 乘以 质数

如果自己是这个质数的倍数，就结束，就避免了重复。

因为大的数能乘到的，他的因数都能乘到。

（不用担心 i + 1 没被筛，i*2 >= i 的。）

vector<int> pri;
bool not_prime[N];void pre(int n) {for (int i = 2; i <= n; ++i) {if (!not_prime[i]) {pri.push_back(i);}for (int pri_j : pri) {if (i * pri_j > n) break;not_prime[i * pri_j] = true;if (i % pri_j == 0) {// i % pri_j == 0// 换言之，i 之前被 pri_j 筛过了// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被// pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break// 掉就好了break;}}}
}

这篇关于Euler 筛法（欧拉筛法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---