原理:根据质数,把这个质数的倍数除去。
void prime(int n,bool a[]){
memset(a,0,sizeof(bool)*(n+1));
a[0]=a[1]=1; //设置为合数
for(int i=2;i*i<=n;i++){
if(a[i]==0){ //质数
for(int j=i<<2;j<=n;j=j+i)
a[j]=1; //把质数的倍数全部设置成合数
}
}
}
2024-01-28 11:02:28
原理:根据质数,把这个质数的倍数除去。
void prime(int n,bool a[]){
memset(a,0,sizeof(bool)*(n+1));
a[0]=a[1]=1; //设置为合数
for(int i=2;i*i<=n;i++){
if(a[i]==0){ //质数
for(int j=i<<2;j<=n;j=j+i)
a[j]=1; //把质数的倍数全部设置成合数
}
}
}