C++で各桁が素数となる最大の数を求める方法

このチュートリアルでは、C++を使って「n以下の数のうち、すべての桁が素数（2・3・5・7）で構成される最大の数」を求めるプログラムを作成します。

一桁の素数は 2、3、5、7 の4つだけです。そのため、答えとなる数はこれらの数字だけで構成されている必要があります。それでは、問題を解くための手順を見ていきましょう。

解法の手順

• 数値nの各桁を先頭から順に走査するループを作成します。
  • 現在の桁が素数でない場合：
    • その桁が「2」以下である間、インデックスiを1つずつ減らします（桁の繰り下がり処理）。iが負になった場合は0に戻します。
    • 現在のインデックスの値を、元の桁より小さい最大の素数の桁に更新します。
    • 次のインデックス以降のすべての桁を「7」（最大の素数の桁）に置き換えます。
• 処理後の文字列nを返します。

実装例

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
bool isPrime(char c) {
   return c == '2' || c == '3' || c == '5' || c == '7';
}
void decrease(string& n, int i) {
   if (n[i] <= '2') {
      n.erase(i, 1);
      n[i] = '7';
   }else if (n[i] == '3') {
      n[i] = '2';
   }else if (n[i] <= '5') {
      n[i] = '3';
   }else if (n[i] <= '7') {
      n[i] = '5';
   }else {
      n[i] = '7';
   }
   return;
}
string getPrimeDigitsNumber(string n) {
   for (int i = 0; i < n.length(); i++) {
      if (!isPrime(n[i])) {
         while (n[i] <= '2' && i >= 0) {
            i--;
         }
         if (i < 0) {
            i = 0;
         }
         decrease(n, i);
         for (int j = i + 1; j < n.length(); j++) {
            n[j] = '7';
         }
         break;
      }
   }
   return n;
}
int main() {
   string n = "7464";
   cout << getPrimeDigitsNumber(n) << endl;
   return 0;
}

出力結果

上記のコードを実行すると、次の結果が出力されます。

7377

動作の解説

入力「7464」の場合、2番目の桁「4」は素数ではありません。そこで、「4」より小さい最大の素数の桁である「3」に置き換えられ、それ以降の桁はすべて最大の素数の桁「7」に設定されます。この処理により、条件を満たす最大の数「7377」が得られます。

まとめ

本チュートリアルについてご不明な点や質問がある場合は、コメント欄でお気軽にお知らせください。