Skip to content

Instantly share code, notes, and snippets.

@peria peria/largest_dpn.cc
Last active Feb 22, 2016

Embed
What would you like to do?
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
You can’t perform that action at this time.