Square-free integers: Difference between revisions
Content added Content deleted
m (Reformatted to reduce line count) |
m (Minor edit to C++ code) |
||
Line 411: | Line 411: | ||
#include <vector> |
#include <vector> |
||
/** |
|||
* A simple implementation of the Sieve of Eratosthenes. |
|||
* See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. |
|||
*/ |
|||
class sieve_of_eratosthenes { |
class sieve_of_eratosthenes { |
||
public: |
public: |
||
Line 416: | Line 420: | ||
bool is_prime(size_t) const; |
bool is_prime(size_t) const; |
||
private: |
private: |
||
std::vector<bool> |
std::vector<bool> is_prime_; |
||
}; |
}; |
||
/** |
|||
⚫ | |||
* Constructs a sieve with the given limit. |
|||
⚫ | |||
* |
|||
⚫ | |||
* @param limit the maximum integer that can be tested for primality |
|||
⚫ | |||
*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) { |
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t limit) { |
||
limit = std::max(size_t(3), |
limit = std::max(size_t(3), limit); |
||
is_prime_.resize(limit/2, true); |
|||
for (size_t p = 3; p * p <= limit; p += 2) { |
for (size_t p = 3; p * p <= limit; p += 2) { |
||
if ( |
if (is_prime_[p/2 - 1]) { |
||
size_t inc = 2 * p; |
size_t inc = 2 * p; |
||
for (size_t q = p * p; q <= limit; q += inc) |
for (size_t q = p * p; q <= limit; q += inc) |
||
is_prime_[q/2 - 1] = false; |
|||
} |
} |
||
} |
} |
||
⚫ | |||
/** |
|||
* 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 |
|||
*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||