质数筛-欧拉筛

对于正常的程序要求，埃氏筛的速度已经是相当不错了，但是在某些极端条件下，埃氏筛的速度可能还不够，这个时候我们就要用到欧拉筛了

思路

埃氏筛存在一个非常严重的缺陷，那就是它会对一个数据进行反复筛选，比如：

6 = 2 * 3

6 = 3 * 2

可以发现，对于 6 这个非质数，我们进行了两次筛选，而对于后面跟大的数来说，可能被筛的次数会更多，这个时候就会对我们筛法的效率产生影响。而欧拉筛法可以避免无效的筛选。

我们发现，对于每个非质数，都会存在唯一的最小质因子。

于是我们便可以让每个和数只在它最小质因子与对应因数相乘时才被标记为合数，这样我们就只筛了一次。例如：

6 = 2 * 3 //标记 6

6 = 3 * 2 //已经标记过，便不再标记

核心思想：从第一个质数开始，一个个排除，不做无效的筛选。

人话：从前向后走，边走边乘，乘出来的数就是合数

代码实现

#include<iostream> #include<cstring> using namespace std; const int N = 1e5; int primes[N]; //存储质数 int flag[N]; //标记是质数还是合数，如果是质数为 0 ,开始假设全是质数 int main(){ int n; cin >> n; int pos = 0; for(int i = 2 ; i <= n ; i++){ if(flag[i] == 0){ //如果是质数 primes[pos++] = i; //存储质数 for(int j = 0 ; j < pos && i * primes[j] <= n ; j++){ flag[primes[j] * i] = 1;//标记为合数 } }else{ //如果是合数 for(int j = 0 ; j < pos && primes[j] * i <= n ; j++){ flag[primes[j] * i] = 1;//标记为合数 if(i % primes[j] == 0) break; //如果可以整除说明发现了最小质因子，退出循环 } } } for(int i = 0 ; i < pos ; i++){ cout << primes[i] << ' '; } cout << endl; return 0; }