C++でN以上の最小の素数回文（プライムパリンドローム）を求める方法

この記事では、「N 以上の整数の中で最小となる素数回文（プライムパリンドローム）」を C++ で求めるアルゴリズムを解説します。

例えば N = 13 の場合、答えは 101 になります。13 以上の回文数には 22、33、44 などがありますが、これらはすべて 11 の倍数であるため素数になり得ません。そのため、次に現れる素数回文である 101 が答えとなります。

解法のアプローチ

全ての整数を順に素数かつ回文かどうか調べるのは非効率です。そこで、回文を直接生成することで探索範囲を大幅に絞り込みます。手順は以下の通りです。

• N が 8 以上 11 以下の場合は、11 を返します（この範囲では 11 だけが素数回文になるための特別なケースです）。

• i を 1 から 99999 までループします。

  • s := i を文字列に変換したもの

  • r := s のコピーを作り、反転（リバース）する

  • num := s と「r の先頭 1 文字を除いた部分文字列」を連結し、数値に変換する（これにより奇数桁の回文が生成されます）

  • num が N 以上であり、かつ素数であれば num を返す

• 最後まで見つからなければ 0 を返します。

なお、偶数桁の回文（11 を除く）は必ず 11 の倍数になるため素数ではありません。この性質により、奇数桁の回文だけを生成すればよいことが分かります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isPrime(int n){
       if(n % 2 == 0 && n > 2) return false;
       for(int i = 3; i * i <= n; i++){
          if(n % i == 0) return false;
       }
       return n != 1 && n != 0;
    }
    int primePalindrome(int N) {
       if(8 <= N && N <= 11) return 11;
       for(int i = 1; i < 100000; i++){
          string s = to_string(i);
          string r = s;
          reverse(r.begin(), r.end());
          int num = stoi(s + r.substr(1));
          if(num >= N && isPrime(num)) return num;
       }
       return 0;
    }
};
main(){
    Solution ob;
    cout << (ob.primePalindrome(105));
}

実行結果

入力

105

出力

131

コードのポイント

例えば i = 13 の場合、s = "13"、r = "31" となり、s + r.substr(1) は "131" になります。このように、元の数字の前半部分を鏡写しにすることで、昇順に近い順序で回文を効率的に生成できます。

素数判定は試し割り法を用いており、√n までの奇数で割り切れるかを確認しています。回文の生成と素数判定を組み合わせることで、単純な全探索よりもはるかに高速に答えを見つけられます。