]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
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. | |
1e59de90 TL |
29 | |
30 | ||
31f18b77 FG |
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. | |
42 | class PrimeTable { | |
43 | public: | |
44 | virtual ~PrimeTable() {} | |
45 | ||
1e59de90 | 46 | // Returns true if and only if n is a prime number. |
31f18b77 FG |
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. | |
55 | class OnTheFlyPrimeTable : public PrimeTable { | |
56 | public: | |
1e59de90 | 57 | bool IsPrime(int n) const override { |
31f18b77 FG |
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 | ||
1e59de90 TL |
68 | int GetNextPrime(int p) const override { |
69 | if (p < 0) return -1; | |
70 | ||
71 | for (int n = p + 1;; n++) { | |
31f18b77 FG |
72 | if (IsPrime(n)) return n; |
73 | } | |
31f18b77 FG |
74 | } |
75 | }; | |
76 | ||
77 | // Implementation #2 pre-calculates the primes and stores the result | |
78 | // in an array. | |
79 | class 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 | } | |
1e59de90 | 86 | ~PreCalculatedPrimeTable() override { delete[] is_prime_; } |
31f18b77 | 87 | |
1e59de90 | 88 | bool IsPrime(int n) const override { |
31f18b77 FG |
89 | return 0 <= n && n < is_prime_size_ && is_prime_[n]; |
90 | } | |
91 | ||
1e59de90 | 92 | int GetNextPrime(int p) const override { |
31f18b77 FG |
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 | ||
1e59de90 TL |
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) { | |
31f18b77 FG |
108 | if (!is_prime_[i]) continue; |
109 | ||
110 | // Marks all multiples of i (except i itself) as non-prime. | |
1e59de90 TL |
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) { | |
31f18b77 FG |
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_ |