C/C++筛选法算素数

）i在2到n-1之间任取一个数,如果n能被整除则不是素数，否则就是素数

普通枚举法: #include <iostream> #include <string> #include <cmath> #include <cstring> using namespace std; bool isPlain(int x){ if(x<2) return false; else{ for(int i=2;i<x;i++) { if(!(x%i)) return false; } } return true; } int main() { int n; cin>>n; int cot=0; for(int j=0;j<n;j++){ if(isPlain(j)){ cout<<j<<((++cot%7==0)?"\n":"\t"); } } } 筛选法:

原始版本:

#include <iostream> #include <string> #include <cmath> #include <cstring> using namespace std; int main() { int n; cin>>n; bool* ans=new bool[n]; memset(ans,true,sizeof(bool)*n);// ans[0]=false; ans[1]=false; for(int i=2;i<n;i++){ if(ans[i]){ for(int j=i*2;j<n;j+=i){//倍数取整 ans[j]=false; } } } int col = 0; for(int i=0;i<n;i++){ if(ans[i]){ cout<<i<<" "; } } return 0; }

改进版本

#include <iostream> #include <string> #include <cmath> #include <cstring> #include <bitset> using namespace std; int main() { int n; cin>>n; bitset<100000> ans; ans.set(0); ans.set(1); for(int j=2; j<=sqrt(n); j++) { for(int i=2*j; i < n; i+=j) { ans.set(i); } } int cot=0; for(int i=0; i<n; i++) { if(ans[i]!=1) { cout<<i<<((++cot%7==0)?"\n":"\t"); } } }