Subversion Repositories s80186

// Copyright 2008 Google Inc.

// All Rights Reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

//     * Neither the name of Google Inc. nor the names of its

// contributors may be used to endorse or promote products derived from

// this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

//

// Author: wan@google.com (Zhanyong Wan)

// Author: vladl@google.com (Vlad Losev)

// This provides interface PrimeTable that determines whether a number is a

// prime and determines a next prime number. This interface is used

// in Google Test samples demonstrating use of parameterized tests.

#ifndef GTEST_SAMPLES_PRIME_TABLES_H_

#define GTEST_SAMPLES_PRIME_TABLES_H_

#include <algorithm>

// The prime table interface.

class PrimeTable {

 public:

  virtual ~PrimeTable() {}

  // Returns true iff n is a prime number.

  virtual bool IsPrime(int n) const = 0;

  // Returns the smallest prime number greater than p; or returns -1

  // if the next prime is beyond the capacity of the table.

  virtual int GetNextPrime(int p) const = 0;

};

// Implementation #1 calculates the primes on-the-fly.

class OnTheFlyPrimeTable : public PrimeTable {

 public:

  virtual bool IsPrime(int n) const {

    if (n <= 1) return false;

    for (int i = 2; i*i <= n; i++) {

      // n is divisible by an integer other than 1 and itself.

      if ((n % i) == 0) return false;

    }

    return true;

  }

  virtual int GetNextPrime(int p) const {

    for (int n = p + 1; n > 0; n++) {

      if (IsPrime(n)) return n;

    }

    return -1;

  }

};

// Implementation #2 pre-calculates the primes and stores the result

// in an array.

class PreCalculatedPrimeTable : public PrimeTable {

 public:

  // 'max' specifies the maximum number the prime table holds.

  explicit PreCalculatedPrimeTable(int max)

      : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) {

    CalculatePrimesUpTo(max);

  }

  virtual ~PreCalculatedPrimeTable() { delete[] is_prime_; }

  virtual bool IsPrime(int n) const {

    return 0 <= n && n < is_prime_size_ && is_prime_[n];

  }

  virtual int GetNextPrime(int p) const {

    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 <= max; i++) {

      if (!is_prime_[i]) continue;

      // Marks all multiples of i (except i itself) as non-prime.

      for (int j = 2*i; j <= max; j += i) {

        is_prime_[j] = false;

      }

    }

  }

  const int is_prime_size_;

  bool* const is_prime_;

  // Disables compiler warning "assignment operator could not be generated."

  void operator=(const PreCalculatedPrimeTable& rhs);

};

#endif  // GTEST_SAMPLES_PRIME_TABLES_H_