1 // Copyright 2008 Google Inc. 2 // All Rights Reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are 6 // met: 7 // 8 // * Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // * Redistributions in binary form must reproduce the above 11 // copyright notice, this list of conditions and the following disclaimer 12 // in the documentation and/or other materials provided with the 13 // distribution. 14 // * Neither the name of Google Inc. nor the names of its 15 // contributors may be used to endorse or promote products derived from 16 // this software without specific prior written permission. 17 // 18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 // This provides interface PrimeTable that determines whether a number is a 31 // prime and determines a next prime number. This interface is used 32 // in Google Test samples demonstrating use of parameterized tests. 33 34 #ifndef GOOGLETEST_SAMPLES_PRIME_TABLES_H_ 35 #define GOOGLETEST_SAMPLES_PRIME_TABLES_H_ 36 37 #include <algorithm> 38 39 // The prime table interface. 40 class PrimeTable { 41 public: 42 virtual ~PrimeTable() = default; 43 44 // Returns true if and only if n is a prime number. 45 virtual bool IsPrime(int n) const = 0; 46 47 // Returns the smallest prime number greater than p; or returns -1 48 // if the next prime is beyond the capacity of the table. 49 virtual int GetNextPrime(int p) const = 0; 50 }; 51 52 // Implementation #1 calculates the primes on-the-fly. 53 class OnTheFlyPrimeTable : public PrimeTable { 54 public: IsPrime(int n)55 bool IsPrime(int n) const override { 56 if (n <= 1) return false; 57 58 for (int i = 2; i * i <= n; i++) { 59 // n is divisible by an integer other than 1 and itself. 60 if ((n % i) == 0) return false; 61 } 62 63 return true; 64 } 65 GetNextPrime(int p)66 int GetNextPrime(int p) const override { 67 if (p < 0) return -1; 68 69 for (int n = p + 1;; n++) { 70 if (IsPrime(n)) return n; 71 } 72 } 73 }; 74 75 // Implementation #2 pre-calculates the primes and stores the result 76 // in an array. 77 class PreCalculatedPrimeTable : public PrimeTable { 78 public: 79 // 'max' specifies the maximum number the prime table holds. PreCalculatedPrimeTable(int max)80 explicit PreCalculatedPrimeTable(int max) 81 : is_prime_size_(std::max(1, max + 1)), 82 is_prime_(new bool[static_cast<size_t>(is_prime_size_)]) { 83 CalculatePrimesUpTo(is_prime_size_ - 1); 84 } ~PreCalculatedPrimeTable()85 ~PreCalculatedPrimeTable() override { delete[] is_prime_; } 86 IsPrime(int n)87 bool IsPrime(int n) const override { 88 return 0 <= n && n < is_prime_size_ && is_prime_[n]; 89 } 90 GetNextPrime(int p)91 int GetNextPrime(int p) const override { 92 for (int n = p + 1; n < is_prime_size_; n++) { 93 if (is_prime_[n]) return n; 94 } 95 96 return -1; 97 } 98 99 private: CalculatePrimesUpTo(int max)100 void CalculatePrimesUpTo(int max) { 101 ::std::fill(is_prime_, is_prime_ + is_prime_size_, true); 102 is_prime_[0] = is_prime_[1] = false; 103 104 // Checks every candidate for prime number (we know that 2 is the only even 105 // prime). 106 for (int i = 2; i * i <= max; i += i % 2 + 1) { 107 if (!is_prime_[i]) continue; 108 109 // Marks all multiples of i (except i itself) as non-prime. 110 // We are starting here from i-th multiplier, because all smaller 111 // complex numbers were already marked. 112 for (int j = i * i; j <= max; j += i) { 113 is_prime_[j] = false; 114 } 115 } 116 } 117 118 const int is_prime_size_; 119 bool* const is_prime_; 120 121 // Disables compiler warning "assignment operator could not be generated." 122 void operator=(const PreCalculatedPrimeTable& rhs); 123 }; 124 125 #endif // GOOGLETEST_SAMPLES_PRIME_TABLES_H_ 126