| 1 | vi prime_sieve(int n) { |
| 2 | int mx = (n - 3) >> 1, sq, v, i = -1; |
| 3 | vi primes; |
| 4 | bool* prime = new bool[mx + 1]; |
| 5 | memset(prime, 1, mx + 1); |
| 6 | if (n >= 2) primes.push_back(2); |
| 7 | while (++i <= mx) if (prime[i]) { |
| 8 | primes.push_back(v = (i << 1) + 3); |
| 9 | if ((sq = i * ((i << 1) + 6) + 3) > mx) break; |
| 10 | for (int j = sq; j <= mx; j += v) prime[j] = false; } |
| 11 | while (++i <= mx) |
| 12 | if (prime[i]) primes.push_back((i << 1) + 3); |
| 13 | delete[] prime; // can be used for O(1) lookup |
| 14 | return primes; } |
| 15 | // vim: cc=60 ts=2 sts=2 sw=2: |