模板——素数筛

 1 int vis[maxn];
 2 int prime[maxn];
 3 
 4 void sieve(int n) {
 5     int m = sqrt(n + 0.5);
 6     memset(m, 0, sizeof m);
 7     for(int i = 2; i <= m; i++) if(!vis[i])
 8         for(int j = i*i; j <= n; j += i) vis[j] = 1;        
 9 }
10 
11 int gen_prime(int n) {
12     sieve(n);
13     int c = 0;
14     for(int i = 2; i <= n; i++) if(!vis[i])
15         prime[c++] = i;
16     return c;   
17 }