对于一个正整数n,我们可以从2到n-1遍历一遍，检查它是不是有除1和自身外的因子，进而判断它是不是素数。
int ay(int n){
for(int i=2;i
可是这种方法看起来不是很聪明哦......简单思考一下，我们其实可以做出如下优化：
对于一个合数n，我们可以知道那些非1和n的因数都是成双成对出现的，它们的边界线是根号n，即对于<=根号n的每一个因数，我们都可以在另一边找到它的cp（流下了寡王的泪水）所以我们其实没必要遍历所有的数对不对？逮住一对cp中的一只就可以hhh
也就是说，我们从2遍历到根号n就OK啦
int ay(int n){
for(int i=2;i*i
同样，我们枚举因数也可以用这个方法——抓住每对cp其中的一只。
OK，仅仅判断一个整数，我们两种算法的复杂度分别是O（n）和O（n^(1/2）)，还是蛮不错的。
但是——当我们要判断很多很多整数的时候，这样的方法所要耗费的时间是很恐怖的，这就需要我们用更加优秀的方法来解决问题。
方法二：埃氏筛法
显然，我们知道对于一个素数，它的倍数必为合数。
利用这个想法，我们可以从2开始，先找到一个素数，然后砍掉该素数所有的倍数。
找到2，砍掉 4,6,8,10...
找到3，砍掉 6,9,12,15...
............
找到哪里为止呢？由前面“cp”的知识我们知道，找到2到根号n中的素数就可以了，一番砍砍砍之后，最后留下的就会全是素数。（YAHOO!!）
#include
#include
#define ll long long
#define maxn 10000001
using namespace std;
int pocket[maxn];
bool data[maxn];
int sieve(int n){
memset(data,true,sizeof(data));
int cnt=0;
data[0]=data[1]=false;
for(int i=2;i<=n;i++){
if(data[i]){
pocket[cnt++]=i;
for(int j=2*i;j<=n;j+=i){
data[j]=false;
}
}
}
return cnt;
}
int main(){
int n;
cin>>n;
cout<
#include
#include
#define ll long long
#define maxn 10000001
using namespace std;
bool data[maxn];
int sieve(int num){
memset(data,true,sizeof(data));
int cnt=0;
data[0]=data[1]=false;
for(int i=2;i*i<=maxn;i++){
if(data[i]){
for(int j=2*i;j<=maxn;j+=i){
data[j]=false;
}
}
}
if(data[num]==1)return 1;
else return 0;
}
int main(){
int n,num;
cin>>n;
for(int i=0;i>num;
if(sieve(num))cout<<"YES"<
埃氏筛的算法复杂度为O（nlog(logn)），在数据量大的时候，秒杀了我们考虑的第一种朴素算法。
方法三：线性筛（欧拉筛）
不对啊，埃氏筛看起来已经很好了，还有什么能改进的吗？
我们来复盘一下过程：
找到2，砍掉4,6,8,10,12...
找到3，砍掉3,6,9,12,15...
找到5，砍掉10,15...
我们发现，在我们砍树数的时候，6、10、12、15这些数字被重复砍了几次，而重复性的工作恰恰拖慢了我们的算法。我们不禁要问，有什么方法可以避免重复砍数嘛？
答案是肯定的——线性筛法
从欧拉那里我们知道了一个事实，即对于任一合数n，有n=maxfactor*p.
其中maxfactor为n的最大因数（该因数的值显然唯一），p为n的最小质因数
更进一步，算数基本定理告诉我们，任一大于1的正整数都可以分解成有限个质数的乘积
所以办法便有了：我们从2开始拿着已有的素数，依次把它们当做最小素因数，分别与后面的素数乘起来得到合数（其实没必要一定是后面的素数，但你懂的，这样更快），砍掉这些合数，从而得到所有的素数。
这种方法的好处是，我们是根据一个合数的最小质因数找到并且砍掉它的，因此对于10、12这种含有多个质因子的合数，我们只会按最小质因数2筛取一次，避免了重复工作。（好耶！！）
代码实现：
#include
#include
const int maxn=10000;
int data[maxn+1];
int cnt=0;
void sieve(){
memset(data,0,sizeof(maxn));
for(int i=2;i<=maxn;i++){
if(!data[i])data[++cnt]=i;
for(int j=1;j<=cnt&&data[j]*i<=maxn;j++){
data[i*data[j]]=1;
if(i%data[j]==0)break; //如果筛过了就跑路继续
}
}
}
int main(){
sieve();
for(int i=1;i<=cnt;i++){
printf("%dn",data[i]);
}
return 0;
}
线性筛把时间复杂度做到了 O（n），比埃氏筛更加优秀（bingo！）
