欧拉筛法(线性素数筛)

 1 #include <cstdio>
 2 #define maxn 100000
 3 int s[maxn],prime[maxn],i,j,cnt; //初始化都是素数
 4 void Prime()
 5 {
 6     for(i = 2; i <= maxn; i++) {
 7         if(!s[i]) prime[++cnt] = i;// cnt,记录素数个数
 8         for(j = 1; j <= cnt && i*prime[j] <= maxn; j++){
 9             s[i*prime[j]] = 1;
10             if(i % prime[j] == 0) break;
11         }
12     }
13 }