素数筛代码

选择素数是用枚举因子的方式是很浪费时间的。

在这里补充一种素数筛。

 1 bool isprime[N];//N 表示范围
 2 int prime[N],cnt; 
 3 void f() 
 4 { 
 5     int i,j; 
 6     cnt=0; 
 7     memset(isprime,true,sizeof(isprime)); 
 8     isprime[1]=false; 
 9     for(i=2;i<=N;i++) 
10     { 
11         if(isprime[i]) 
12         { 
13             prime[cnt++]=i;//记录素数
14             for(j=i*i;j<=N;j+=i)
15                 isprime[j]=false; 
16         } 
17     } 
　　}
注意：

每次去寻找它的倍数然后置为0
因为小于 i 的所有的倍数都被筛过，所以直接从 i*i 开始，从这里也可以看出，筛素数时到 N^0.5 就可以了