Safe primes and unsafe primes: Difference between revisions
m
Minor edit to C++ code
m (Reformatted to reduce line count) |
m (Minor edit to C++ code) |
||
Line 328:
#include <vector>
/**
* A simple implementation of the Sieve of Eratosthenes.
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
*/
class sieve_of_eratosthenes {
public:
Line 333 ⟶ 337:
bool is_prime(size_t) const;
private:
std::vector<bool>
};
/**
inline bool sieve_of_eratosthenes::is_prime(size_t n) const {▼
* Constructs a sieve with the given limit.
if (n == 2)▼
*
return true;▼
* @param limit the maximum integer that can be tested for primality
if (n < 2 || n % 2 == 0)▼
*/
return false;▼
return odd_prime_[n/2 - 1];▼
}▼
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) {
limit = std::max(size_t(3),
for (size_t p = 3; p * p <= limit; p += 2) {
if (
size_t inc = 2 * p;
for (size_t q = p * p; q <= limit; q += inc)
}
}
▲}
/**
* Returns true if the given integer is a prime number. The integer
* must be less than or equal to the limit passed to the constructor.
*
* @param n an integer less than or equal to the limit passed to the
* constructor
* @return true if the integer is prime
*/
▲inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
▲ if (n == 2)
▲ return true;
▲ if (n < 2 || n % 2 == 0)
▲ return false;
}
| |||