Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
枚数毎の最大素数大富豪素数を求めるプログラムです
#include <gmpxx.h>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
const char* cards[] = {"", "1", "2", "3", "4", "5", "6",
"7", "8", "9", "10", "11", "12", "13"};
const int kAllCards = 13 * 4 + 2;
string getLargestPrime(vector<string>& deck, int num) {
auto comp = [](const string& a, const string& b) -> bool {
if (a.size() == b.size()) return a > b;
return a.size() > b.size();
};
sort(deck.begin(), deck.end(), comp);
auto begin = deck.begin();
auto sbegin = begin + ((num <= 13) ? 0 : (num - 13));
auto end = begin + ((num <= 18) ? 18 : num);
sort(begin, end, greater<string>());
// Check if the deck makes only multiples of 3.
if (num >= 18) {
int mod3 = 0;
for (auto i = begin; i != end; ++i) {
mod3 += strtoll(i->c_str(), nullptr, 10);
}
if (mod3 % 3 == 0) {
return "";
}
}
// In case we don't include Ace cards, we rearrange
// only 2-digits cards. Then we can check if it always
// makes multiples of 11.
if (num <= 50) {
int mod11 = 0;
for (auto i = begin; i != sbegin; ++i) {
mod11 = (mod11 + strtoll(i->c_str(), nullptr, 10)) % 11;
}
for (auto i = sbegin; i != end; ++i) {
mod11 += strtoll(i->c_str(), nullptr, 10);
}
if (mod11 % 11 == 0) {
return "";
}
}
string largest;
do {
string value;
for (int i = 0; i < num; ++i) value.append(deck[i]);
if (mpz_probab_prime_p(mpz_class(value.c_str()).get_mpz_t(), 20)) {
if (largest.size() < value.size() || largest < value) {
largest = value;
if (num <= 50) break;
}
}
reverse(sbegin + num, end);
} while (next_permutation(sbegin, end, greater<string>()));
return largest;
}
int main() {
vector<string> deckKK, deckKQ, deckQQ;
for (int i = 1; i <= 13; ++i) {
for (int j = 0; j < 4; ++j) deckKK.push_back(cards[i]);
}
deckQQ = deckKQ = deckKK;
deckKK.push_back("13");
deckKK.push_back("13");
deckKQ.push_back("13");
deckKQ.push_back("12");
deckQQ.push_back("12");
deckQQ.push_back("12");
for (int num_cards = 1; num_cards <= kAllCards; ++num_cards) {
string largestKK = getLargestPrime(deckKK, num_cards);
string largestKQ = getLargestPrime(deckKQ, num_cards);
string largestQQ = getLargestPrime(deckQQ, num_cards);
if (largestKK < largestKQ) largestKK = largestKQ;
if (largestKK < largestQQ) largestKK = largestQQ;
cout << "| " << num_cards << " | " << largestKK << " |\n";
}
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.