Qucs-core
0.0.19
|
00001 // Copyright 2008 Google Inc. 00002 // All Rights Reserved. 00003 // 00004 // Redistribution and use in source and binary forms, with or without 00005 // modification, are permitted provided that the following conditions are 00006 // met: 00007 // 00008 // * Redistributions of source code must retain the above copyright 00009 // notice, this list of conditions and the following disclaimer. 00010 // * Redistributions in binary form must reproduce the above 00011 // copyright notice, this list of conditions and the following disclaimer 00012 // in the documentation and/or other materials provided with the 00013 // distribution. 00014 // * Neither the name of Google Inc. nor the names of its 00015 // contributors may be used to endorse or promote products derived from 00016 // this software without specific prior written permission. 00017 // 00018 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 00019 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 00020 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 00021 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 00022 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00023 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 00024 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 00028 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // Author: wan@google.com (Zhanyong Wan) 00031 // Author: vladl@google.com (Vlad Losev) 00032 00033 // This provides interface PrimeTable that determines whether a number is a 00034 // prime and determines a next prime number. This interface is used 00035 // in Google Test samples demonstrating use of parameterized tests. 00036 00037 #ifndef GTEST_SAMPLES_PRIME_TABLES_H_ 00038 #define GTEST_SAMPLES_PRIME_TABLES_H_ 00039 00040 #include <algorithm> 00041 00042 // The prime table interface. 00043 class PrimeTable { 00044 public: 00045 virtual ~PrimeTable() {} 00046 00047 // Returns true iff n is a prime number. 00048 virtual bool IsPrime(int n) const = 0; 00049 00050 // Returns the smallest prime number greater than p; or returns -1 00051 // if the next prime is beyond the capacity of the table. 00052 virtual int GetNextPrime(int p) const = 0; 00053 }; 00054 00055 // Implementation #1 calculates the primes on-the-fly. 00056 class OnTheFlyPrimeTable : public PrimeTable { 00057 public: 00058 virtual bool IsPrime(int n) const { 00059 if (n <= 1) return false; 00060 00061 for (int i = 2; i*i <= n; i++) { 00062 // n is divisible by an integer other than 1 and itself. 00063 if ((n % i) == 0) return false; 00064 } 00065 00066 return true; 00067 } 00068 00069 virtual int GetNextPrime(int p) const { 00070 for (int n = p + 1; n > 0; n++) { 00071 if (IsPrime(n)) return n; 00072 } 00073 00074 return -1; 00075 } 00076 }; 00077 00078 // Implementation #2 pre-calculates the primes and stores the result 00079 // in an array. 00080 class PreCalculatedPrimeTable : public PrimeTable { 00081 public: 00082 // 'max' specifies the maximum number the prime table holds. 00083 explicit PreCalculatedPrimeTable(int max) 00084 : is_prime_size_(max + 1), is_prime_(new bool[max + 1]) { 00085 CalculatePrimesUpTo(max); 00086 } 00087 virtual ~PreCalculatedPrimeTable() { delete[] is_prime_; } 00088 00089 virtual bool IsPrime(int n) const { 00090 return 0 <= n && n < is_prime_size_ && is_prime_[n]; 00091 } 00092 00093 virtual int GetNextPrime(int p) const { 00094 for (int n = p + 1; n < is_prime_size_; n++) { 00095 if (is_prime_[n]) return n; 00096 } 00097 00098 return -1; 00099 } 00100 00101 private: 00102 void CalculatePrimesUpTo(int max) { 00103 ::std::fill(is_prime_, is_prime_ + is_prime_size_, true); 00104 is_prime_[0] = is_prime_[1] = false; 00105 00106 for (int i = 2; i <= max; i++) { 00107 if (!is_prime_[i]) continue; 00108 00109 // Marks all multiples of i (except i itself) as non-prime. 00110 for (int j = 2*i; j <= max; j += i) { 00111 is_prime_[j] = false; 00112 } 00113 } 00114 } 00115 00116 const int is_prime_size_; 00117 bool* const is_prime_; 00118 00119 // Disables compiler warning "assignment operator could not be generated." 00120 void operator=(const PreCalculatedPrimeTable& rhs); 00121 }; 00122 00123 #endif // GTEST_SAMPLES_PRIME_TABLES_H_