123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126 |
- #ifndef GOOGLETEST_SAMPLES_PRIME_TABLES_H_
- #define GOOGLETEST_SAMPLES_PRIME_TABLES_H_
- #include <algorithm>
- class PrimeTable {
- public:
- virtual ~PrimeTable() {}
-
- virtual bool IsPrime(int n) const = 0;
-
-
- virtual int GetNextPrime(int p) const = 0;
- };
- class OnTheFlyPrimeTable : public PrimeTable {
- public:
- bool IsPrime(int n) const override {
- if (n <= 1) return false;
- for (int i = 2; i*i <= n; i++) {
-
- if ((n % i) == 0) return false;
- }
- return true;
- }
- int GetNextPrime(int p) const override {
- if (p < 0) return -1;
- for (int n = p + 1;; n++) {
- if (IsPrime(n)) return n;
- }
- }
- };
- class PreCalculatedPrimeTable : public PrimeTable {
- public:
-
- explicit PreCalculatedPrimeTable(int max)
- : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) {
- CalculatePrimesUpTo(max);
- }
- ~PreCalculatedPrimeTable() override { delete[] is_prime_; }
- bool IsPrime(int n) const override {
- return 0 <= n && n < is_prime_size_ && is_prime_[n];
- }
- int GetNextPrime(int p) const override {
- for (int n = p + 1; n < is_prime_size_; n++) {
- if (is_prime_[n]) return n;
- }
- return -1;
- }
- private:
- void CalculatePrimesUpTo(int max) {
- ::std::fill(is_prime_, is_prime_ + is_prime_size_, true);
- is_prime_[0] = is_prime_[1] = false;
-
-
- for (int i = 2; i*i <= max; i += i%2+1) {
- if (!is_prime_[i]) continue;
-
-
-
- for (int j = i*i; j <= max; j += i) {
- is_prime_[j] = false;
- }
- }
- }
- const int is_prime_size_;
- bool* const is_prime_;
-
- void operator=(const PreCalculatedPrimeTable& rhs);
- };
- #endif
|