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 31 32// This provides interface PrimeTable that determines whether a number is a 33// prime and determines a next prime number. This interface is used 34// in Google Test samples demonstrating use of parameterized tests. 35 36#ifndef GTEST_SAMPLES_PRIME_TABLES_H_ 37#define GTEST_SAMPLES_PRIME_TABLES_H_ 38 39#include <algorithm> 40 41// The prime table interface. 42class PrimeTable { 43 public: 44 virtual ~PrimeTable() {} 45 46 // Returns true iff n is a prime number. 47 virtual bool IsPrime(int n) const = 0; 48 49 // Returns the smallest prime number greater than p; or returns -1 50 // if the next prime is beyond the capacity of the table. 51 virtual int GetNextPrime(int p) const = 0; 52}; 53 54// Implementation #1 calculates the primes on-the-fly. 55class OnTheFlyPrimeTable : public PrimeTable { 56 public: 57 virtual bool IsPrime(int n) const { 58 if (n <= 1) return false; 59 60 for (int i = 2; i*i <= n; i++) { 61 // n is divisible by an integer other than 1 and itself. 62 if ((n % i) == 0) return false; 63 } 64 65 return true; 66 } 67 68 virtual int GetNextPrime(int p) const { 69 for (int n = p + 1; n > 0; n++) { 70 if (IsPrime(n)) return n; 71 } 72 73 return -1; 74 } 75}; 76 77// Implementation #2 pre-calculates the primes and stores the result 78// in an array. 79class PreCalculatedPrimeTable : public PrimeTable { 80 public: 81 // 'max' specifies the maximum number the prime table holds. 82 explicit PreCalculatedPrimeTable(int max) 83 : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) { 84 CalculatePrimesUpTo(max); 85 } 86 virtual ~PreCalculatedPrimeTable() { delete[] is_prime_; } 87 88 virtual bool IsPrime(int n) const { 89 return 0 <= n && n < is_prime_size_ && is_prime_[n]; 90 } 91 92 virtual int GetNextPrime(int p) const { 93 for (int n = p + 1; n < is_prime_size_; n++) { 94 if (is_prime_[n]) return n; 95 } 96 97 return -1; 98 } 99 100 private: 101 void CalculatePrimesUpTo(int max) { 102 ::std::fill(is_prime_, is_prime_ + is_prime_size_, true); 103 is_prime_[0] = is_prime_[1] = false; 104 105 // Checks every candidate for prime number (we know that 2 is the only even 106 // prime). 107 for (int i = 2; i*i <= max; i += i%2+1) { 108 if (!is_prime_[i]) continue; 109 110 // Marks all multiples of i (except i itself) as non-prime. 111 // We are starting here from i-th multiplier, because all smaller 112 // complex numbers were already marked. 113 for (int j = i*i; j <= max; j += i) { 114 is_prime_[j] = false; 115 } 116 } 117 } 118 119 const int is_prime_size_; 120 bool* const is_prime_; 121 122 // Disables compiler warning "assignment operator could not be generated." 123 void operator=(const PreCalculatedPrimeTable& rhs); 124}; 125 126#endif // GTEST_SAMPLES_PRIME_TABLES_H_ 127