质数筛-埃氏筛

质数的定义：只能被 1 和它自身整除的数

优势

相比于暴力的筛法，埃氏筛的算法效率要快不少，虽然比起欧拉筛来说，埃氏筛的优化仍然有待提高。但比起欧拉筛，埃氏筛的理解难度要小不少。

埃氏筛介绍

埃氏筛的时间复杂度在O()

我们可以想到一点，任何数的倍数都不可能为质数，所以我们可以因此来抹去一些与一个数倍数相关的数。其实就是空间换时间的想法

代码部分

暴力筛

#include<iostream> using namespace std; int main(){ int n; cin >> n; //判断 n 是不是质数 int flag = 1; if(n == 1){ flag = 0; }else{ for(int i = 2 ; i < n ; i++){ if(n % i == 0) flag = 0; } } //是质数输出yes，反之输出no if(flag) cout << "yes" << endl; else cout << "no" << endl; return 0; }

当然，在实际的使用中，你也可以通过打表的方法来提高筛法的效率。当然，在算法比赛中，很多时候你打出来的表不一定管用。

循环也可以把遍历的条件改成 i <=， 这样也可以提高效率

埃氏筛

#include<iostream> #include<cstring> using namespace std; const int N = 1e5; int flag[N]; int main(){ int n; cin >> n; //把flag全初始化为 1(除了 0 和 1) memset(flag , 1 ,sizeof(flag)); flag[0] = 0; flag[1] = 0; //开始筛，质数的倍数全都打上标记 for(int i = 2 ; i * i <= n ; i++){ for(int j = i * 2 ; j <= n ; j += i){ flag[j] = 0; } } //输出 for(int i = 0 ; i < n ; i++){ if(flag[i]) cout << i << ' '; } cout << endl; return 0; }