Truncatable primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
m (Put Sieve of Eratosthenes implementation in separate header file) |
||
Line 529: | Line 529: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
<lang cpp>#include <iostream> |
<lang cpp>#include <iostream> |
||
#include |
#include "sieve_of_eratosthenes.h" |
||
int main() |
int main() |
||
Line 536: | Line 536: | ||
// find the prime numbers up to the limit |
// find the prime numbers up to the limit |
||
sieve_of_eratosthenes sieve(limit + 1); |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
int largest_left = 0; |
int largest_left = 0; |
||
int largest_right = 0; |
int largest_right = 0; |
||
Line 551: | Line 543: | ||
for (int p = limit; p >= 2; --p) |
for (int p = limit; p >= 2; --p) |
||
{ |
{ |
||
if (! |
if (!sieve.is_prime(p)) |
||
continue; |
continue; |
||
bool left_truncatable = true; |
bool left_truncatable = true; |
||
for (int n = 10, q = p; p > n; n *= 10) |
for (int n = 10, q = p; p > n; n *= 10) |
||
{ |
{ |
||
if (! |
if (!sieve.is_prime(p % n) || q == p % n) |
||
{ |
{ |
||
left_truncatable = false; |
left_truncatable = false; |
||
Line 572: | Line 564: | ||
for (int p = limit; p >= 2; --p) |
for (int p = limit; p >= 2; --p) |
||
{ |
{ |
||
if (! |
if (!sieve.is_prime(p)) |
||
continue; |
continue; |
||
bool right_truncatable = true; |
bool right_truncatable = true; |
||
for (int q = p/10; q > 0; q /= 10) |
for (int q = p/10; q > 0; q /= 10) |
||
{ |
{ |
||
if (! |
if (!sieve.is_prime(q)) |
||
{ |
{ |
||
right_truncatable = false; |
right_truncatable = false; |
||
Line 594: | Line 586: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
Contents of sieve_of_eratosthenes.h: |
|||
<lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H |
|||
#define SIEVE_OF_ERATOSTHENES_H |
|||
#include <vector> |
|||
class sieve_of_eratosthenes |
|||
{ |
|||
public: |
|||
explicit sieve_of_eratosthenes(size_t); |
|||
bool is_prime(size_t) const; |
|||
private: |
|||
std::vector<bool> is_prime_; |
|||
}; |
|||
inline bool sieve_of_eratosthenes::is_prime(size_t n) const |
|||
{ |
|||
return is_prime_[n]; |
|||
} |
|||
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t max) |
|||
: is_prime_(max, true) |
|||
{ |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
#endif</lang> |
|||
{{out}} |
{{out}} |