Find largest left truncatable prime in a given base: Difference between revisions
Find largest left truncatable prime in a given base (view source)
Revision as of 12:42, 8 May 2022
, 2 years agoAdded C++ solution
m (→{{header|Phix}}: added syntax colouring the hard way) |
(Added C++ solution) |
||
Line 201:
00:00:00.0003609 11 2276005673
00:00:03.3792076 12 13092430647736190817303130065827539
</pre>
=={{header|C++}}==
{{trans|C}}
<lang cpp>#include <gmpxx.h>
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
using big_int = mpz_class;
const unsigned int small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23,
29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97};
bool is_probably_prime(const big_int& n, int reps) {
return mpz_probab_prime_p(n.get_mpz_t(), reps) != 0;
}
big_int largest_left_truncatable_prime(unsigned int base) {
std::vector<big_int> powers = {1};
std::vector<big_int> value = {0};
big_int result = 0;
std::function<void(unsigned int)> add_digit = [&](unsigned int i) {
if (i == value.size()) {
value.resize(i + 1);
powers.push_back(base * powers.back());
}
for (unsigned int d = 1; d < base; ++d) {
value[i] = value[i - 1] + powers[i] * d;
if (!is_probably_prime(value[i], 1))
continue;
if (value[i] > result) {
if (!is_probably_prime(value[i], 50))
continue;
result = value[i];
}
add_digit(i + 1);
}
};
for (unsigned int i = 0; small_primes[i] < base; ++i) {
value[0] = small_primes[i];
add_digit(1);
}
return result;
}
int main() {
for (unsigned int base = 3; base < 18; ++base) {
std::cout << base << ": " << largest_left_truncatable_prime(base)
<< '\n';
}
for (unsigned int base = 19; base < 32; base += 2) {
std::cout << base << ": " << largest_left_truncatable_prime(base)
<< '\n';
}
}</lang>
{{out}}
<pre>
3: 23
4: 4091
5: 7817
6: 4836525320399
7: 817337
8: 14005650767869
9: 1676456897
10: 357686312646216567629137
11: 2276005673
12: 13092430647736190817303130065827539
13: 812751503
14: 615419590422100474355767356763
15: 34068645705927662447286191
16: 1088303707153521644968345559987
17: 13563641583101
19: 546207129080421139
21: 391461911766647707547123429659688417
23: 116516557991412919458949
25: 8211352191239976819943978913
27: 10681632250257028944950166363832301357693
29: 4300289072819254369986567661
31: 645157007060845985903112107793191
</pre>
| |||