C++的素数筛

素数筛素数是大于1并且除了1和它本身不能被其他自然数整除的自然数。最小的自然数是2也是唯一的偶素数1、暴力枚举n1e4#includebits/stdc.h using namespace std; # define int long long //判断单个数字是不是素数 int isp(int num){ if(num2){ return 0;//小于2的都不是素数 } //只遍历到根号num,减少循环次数 for(int i2;i*inum;i){ if(num%i0){ return 0;//能被整除的就不是素数结束 } } return 1;//是素数 } signed main(){ int x; cinx; if(isp(x)){//调用函数判断是不是素数 coutY; } else{ coutN; } return 0; }2、埃氏筛定义一个布尔数组isp[],isp[i]表示数字i是否是素数初始全设置为素数为真从最小的素数2开始将所有2的倍数标记为假依次遍历后续数字如果当前是素数就标记素数所有的倍数为假最终数组中值为真的下标就是1到N中所有的素数#includebits/stdc.h using namespace std; #define int long long const int N10005; bool isp[N]; void solve(){ //初始化先默认所有的数都是素数为真 for(int i2;iN;i){ isp[i]true; } for(int i2;i*iN;i){ if(isp[i]){//如果i是素数标记它的所有倍数为假 for(int ji*i;jN;ji){ isp[j]false; } } } } signed main(){ solve(); int x; cinx; if(isp[x]){ coutyendl; } else{ coutn; } return 0; }