## "Fossies" - the Fresh Open Source Software Archive skipping to change at line 58 skipping to change at line 58
// if the next prime is beyond the capacity of the table. // if the next prime is beyond the capacity of the table.
virtual int GetNextPrime(int p) const = 0; virtual int GetNextPrime(int p) const = 0;
}; };
// Implementation #1 calculates the primes on-the-fly. // Implementation #1 calculates the primes on-the-fly.
class OnTheFlyPrimeTable : public PrimeTable { class OnTheFlyPrimeTable : public PrimeTable {
public: public:
bool IsPrime(int n) const override { bool IsPrime(int n) const override {
if (n <= 1) return false; if (n <= 1) return false;
for (int i = 2; ii <= n; i++) { for (int i = 2; i * i <= n; i++) {
// n is divisible by an integer other than 1 and itself. // n is divisible by an integer other than 1 and itself.
if ((n % i) == 0) return false; if ((n % i) == 0) return false;
} }
return true; return true;
} }
int GetNextPrime(int p) const override { int GetNextPrime(int p) const override {
if (p < 0) return -1; if (p < 0) return -1;
skipping to change at line 105 skipping to change at line 105
return -1; return -1;
} }
private: private:
void CalculatePrimesUpTo(int max) { void CalculatePrimesUpTo(int max) {
::std::fill(is_prime_, is_prime_ + is_prime_size_, true); ::std::fill(is_prime_, is_prime_ + is_prime_size_, true);
is_prime_ = is_prime_ = false; is_prime_ = is_prime_ = false;
// Checks every candidate for prime number (we know that 2 is the only even // Checks every candidate for prime number (we know that 2 is the only even
// prime). // prime).
for (int i = 2; i1) { for (int i = 2; i * i <= max; i += i % 2 + 1) {
if (!is_prime_[i]) continue; if (!is_prime_[i]) continue;
// Marks all multiples of i (except i itself) as non-prime. // Marks all multiples of i (except i itself) as non-prime.
// We are starting here from i-th multiplier, because all smaller // We are starting here from i-th multiplier, because all smaller
// complex numbers were already marked. // complex numbers were already marked.
for (int j = ii; j <= max; j += i) { for (int j = i * i; j <= max; j += i) {
is_prime_[j] = false; is_prime_[j] = false;
} }
} }
} }
const int is_prime_size_; const int is_prime_size_;
bool* const is_prime_; bool* const is_prime_;
// Disables compiler warning "assignment operator could not be generated." // Disables compiler warning "assignment operator could not be generated."
void operator=(const PreCalculatedPrimeTable& rhs); void operator=(const PreCalculatedPrimeTable& rhs);
End of changes. 3 change blocks.
3 lines changed or deleted 3 lines changed or added