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