Truncatable primes: Difference between revisions
Content deleted Content added
→{{header|Wren}}: Now uses Wren-math module. |
m Minor edit to C++ code |
||
Line 529: | Line 529: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include " |
#include "sieve_of_eratosthenes.h" |
||
bool is_left_truncatable(const sieve_of_eratosthenes& sieve, int p) { |
bool is_left_truncatable(const sieve_of_eratosthenes& sieve, int p) { |
||
Line 583: | Line 583: | ||
#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 588: | Line 592: | ||
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 |
|||
*/ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||