线性筛质数

原理:根据质数,把这个质数的倍数除去。

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;  //把质数的倍数全部设置成合数 
		}
	}
} 
上一篇:C语言内置函数memset用法


下一篇:AcWing 3250. 通信网络 两次bfs