81 : is_prime_size_(max + 1), is_prime_(
new bool[max + 1]) {
82 CalculatePrimesUpTo(max);
86 bool IsPrime(
int n)
const override {
87 return 0 <= n && n < is_prime_size_ && is_prime_[n];
90 int GetNextPrime(
int p)
const override {
91 for (
int n = p + 1; n < is_prime_size_; n++) {
92 if (is_prime_[n])
return n;
99 void CalculatePrimesUpTo(
int max) {
100 ::std::fill(is_prime_, is_prime_ + is_prime_size_,
true);
101 is_prime_[0] = is_prime_[1] =
false;
105 for (
int i = 2; i * i <= max; i += i % 2 + 1) {
106 if (!is_prime_[i])
continue;
111 for (
int j = i * i; j <= max; j += i) {
112 is_prime_[j] =
false;
117 const int is_prime_size_;
118 bool*
const is_prime_;