素数筛

对于一些题，我们需要去枚举n以下的素数，
但是有时可能不止一个数需要这样做，所以下面介绍一些筛出n以下的素数的方法
一.暴力求解
直接枚举每一个\(i\in[2,n]\)，判断其是否是素数，然后加入数组
判断素数的话枚举\(j\in[2,\sqrt i]\),判断是否i能整除j，若都不能，则i为素数
代码比较简单，时间复杂度最高，为\(O(n\sqrt n)\)

for(int i=2;i<=n;i++){
	bool f=true;;
	for(int j=2;j<=sqrt(i);j++)if(i%j==0)f=false;
	if(f)cout<<i<<endl;
}

输出的即为n以内的所有素数

素数筛

原文：https://www.cnblogs.com/yang-RA-NOI/p/13434831.html