线筛

 1 bool b[maxn];
 2 int f[maxn],len;
 3 void init(int n){
 4     b[0]=b[1]=1;
 5     for(int i=2;i<=n;i++)
 6     {
 7         if(!b[i])
 8         f[++len]=i;  
 9         for(int j=1;j<=len;j++)
10         {
11             if(i*f[j]>n)break;
12             b[i*f[j]]=1;
13             if(i%f[j]==0)break;//如果i是prime[j]的倍数，那么在筛i时已经筛过prime[j]的倍数了，所以跳出
14         }
15     }
16 }