Check if the largest prime number in Prime-Daifugo can have 71 digits?
#include <gmpxx.h> | |
#include <algorithm> | |
#include <functional> | |
#include <iostream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
const char* ranks[] = {"", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13"}; | |
// A candidate is 99998888777766665555444433332222131313131313121212121111111011010101111 | |
int main() { | |
vector<string> cards; | |
for (int i = 1; i <= 13; ++i) { | |
int num = (i == 1) ? 3 : ((i == 13) ? 6 : 4); | |
for (int j = 0; j < num; ++j) { | |
cards.push_back(ranks[i]); | |
} | |
} | |
sort(cards.begin(), cards.end(), greater<string>()); | |
// Split the array into prefix part and suffix part. | |
// Suffix part is made of "1", "10", and "11". | |
vector<string>::iterator suffix; | |
string prefix; | |
for (suffix = cards.begin(); suffix != cards.end(); ++suffix) { | |
const string& c = *suffix; | |
if (c == "11") { | |
break; | |
} | |
prefix.append(c); | |
} | |
string largest("99998888777766665555444433332222131313131313121212121111111011010101111"); | |
cout << largest << "\n"; | |
do { | |
string value(prefix); | |
for (auto it = suffix; it != cards.end(); ++it) | |
value.append(*it); | |
int ret = mpz_probab_prime_p(mpz_class(value.c_str()).get_mpz_t(), 100); | |
if (ret && value > largest) { | |
cout << value << "\n"; | |
largest = value; | |
} | |
} while(next_permutation(suffix, cards.end(), greater<string>())); | |
return 0; | |
} |
#include <gmpxx.h> | |
#include <algorithm> | |
#include <functional> | |
#include <iostream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
const char* ranks[] = {"", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13"}; | |
int main() { | |
vector<string> cards; | |
for (int i = 1; i <= 13; ++i) { | |
int num = (i == 1) ? 3 : ((i == 13) ? 6 : 4); | |
for (int j = 0; j < num; ++j) { | |
cards.push_back(ranks[i]); | |
} | |
} | |
sort(cards.begin(), cards.end(), greater<string>()); | |
do { | |
string value; | |
for (const string& c : cards) | |
value += c; | |
int ret = mpz_probab_prime_p(mpz_class(value.c_str()).get_mpz_t(), 100); | |
if (ret) { | |
cout << value << "\n"; | |
break; | |
} | |
} while(next_permutation(cards.begin(), cards.end(), greater<string>())); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment