1234567891011121314151617 |
- const int maxn = 10000005;
- const int maxp = 700000;
- int vis[maxn]; //0 for prime number
- int prime[maxp];
- void sieve(int n){
- int m = (int)sqrt(n+0.5);
- memset(vis, 0, sizeof(vis));
- for (int i = 2; i <= m, i++) if (!vis[i])
- for (int j = i*i; j <= n; j += i) vis[j] = 1;
- }
- int gen_primes(int n) {
- sieve(n);
- int c = 0;
- for (int i = 2; i <= n; i++) if (!vis[i])
- prime[c++] = i;
- return c;
- }
|