Palindromic primes: Difference between revisions
Added C++ solution
(Added C++ solution) |
|||
Line 160:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Palindromic primes 1-999: 20
</pre>
=={{header|C++}}==
This includes a solution for the similar task [[Palindromic primes in base 16]].
<lang cpp>#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
unsigned int reverse(unsigned int base, unsigned int n) {
unsigned int rev = 0;
for (; n > 0; n /= base)
rev = rev * base + (n % base);
return rev;
}
class palindrome_generator {
public:
explicit palindrome_generator(unsigned int base)
: base_(base), upper_(base) {}
unsigned int next_palindrome();
private:
unsigned int base_;
unsigned int lower_ = 1;
unsigned int upper_;
unsigned int next_ = 0;
bool even_ = false;
};
unsigned int palindrome_generator::next_palindrome() {
++next_;
if (next_ == upper_) {
if (even_) {
lower_ = upper_;
upper_ *= base_;
}
next_ = lower_;
even_ = !even_;
}
return even_ ? next_ * upper_ + reverse(base_, next_)
: next_ * lower_ + reverse(base_, next_ / base_);
}
bool is_prime(unsigned int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
std::string to_string(unsigned int base, unsigned int n) {
assert(base <= 36);
static constexpr char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::string str;
for (; n != 0; n /= base)
str += digits[n % base];
std::reverse(str.begin(), str.end());
return str;
}
void print_palindromic_primes(unsigned int base, unsigned int limit) {
auto width =
static_cast<unsigned int>(std::ceil(std::log(limit) / std::log(base)));
unsigned int count = 0;
auto columns = 80 / (width + 1);
std::cout << "Base " << base << " palindromic primes less than " << limit
<< ":\n";
palindrome_generator pgen(base);
unsigned int palindrome;
while ((palindrome = pgen.next_palindrome()) < limit) {
if (is_prime(palindrome)) {
++count;
std::cout << std::setw(width) << to_string(base, palindrome)
<< (count % columns == 0 ? '\n' : ' ');
}
}
if (count % columns != 0)
std::cout << '\n';
std::cout << "Count: " << count << '\n';
}
void count_palindromic_primes(unsigned int base, unsigned int limit) {
unsigned int count = 0;
palindrome_generator pgen(base);
unsigned int palindrome;
while ((palindrome = pgen.next_palindrome()) < limit)
if (is_prime(palindrome))
++count;
std::cout << "Number of base " << base << " palindromic primes less than "
<< limit << ": " << count << '\n';
}
int main() {
print_palindromic_primes(10, 1000);
std::cout << '\n';
print_palindromic_primes(10, 100000);
std::cout << '\n';
count_palindromic_primes(10, 1000000000);
std::cout << '\n';
print_palindromic_primes(16, 500);
}</lang>
{{out}}
<pre>
Base 10 palindromic primes less than 1000:
2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929
Count: 20
Base 10 palindromic primes less than 100000:
2 3 5 7 11 101 131 151 181 191 313 353 373
383 727 757 787 797 919 929 10301 10501 10601 11311 11411 12421
12721 12821 13331 13831 13931 14341 14741 15451 15551 16061 16361 16561 16661
17471 17971 18181 18481 19391 19891 19991 30103 30203 30403 30703 30803 31013
31513 32323 32423 33533 34543 34843 35053 35153 35353 35753 36263 36563 37273
37573 38083 38183 38783 39293 70207 70507 70607 71317 71917 72227 72727 73037
73237 73637 74047 74747 75557 76367 76667 77377 77477 77977 78487 78787 78887
79397 79697 79997 90709 91019 93139 93239 93739 94049 94349 94649 94849 94949
95959 96269 96469 96769 97379 97579 97879 98389 98689
Count: 113
Number of base 10 palindromic primes less than 1000000000: 5953
Base 16 palindromic primes less than 500:
2 3 5 7 B D 11 101 151 161 191 1B1 1C1
Count: 13
</pre>
| |||