枚数毎の最大素数大富豪素数を求めるプログラムです

largest_dpn_for_each.cc

#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;
}