34#ifndef GOOGLETEST_SAMPLES_PRIME_TABLES_H_
35#define GOOGLETEST_SAMPLES_PRIME_TABLES_H_
56 if (n <= 1)
return false;
58 for (
int i = 2; i * i <= n; i++) {
60 if ((n % i) == 0)
return false;
69 for (
int n = p + 1;; n++) {
81 : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) {
82 CalculatePrimesUpTo(max);
87 return 0 <= n && n < is_prime_size_ && is_prime_[n];
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_;
int GetNextPrime(int p) const override
bool IsPrime(int n) const override
int GetNextPrime(int p) const override
bool IsPrime(int n) const override
PreCalculatedPrimeTable(int max)
~PreCalculatedPrimeTable() override
virtual bool IsPrime(int n) const =0
virtual int GetNextPrime(int p) const =0