C++で次の回文素数を見つける方法【効率的なアルゴリズムを解説】

問題概要

この記事では、与えられた整数 N に対して「N より大きい最小の回文素数」を求めるアルゴリズムを、C++ の実装例とともに解説します。

問題の定義： N より大きい数の中から、素数でありかつ回文数でもある最小の数を見つけます。

回文数とは、左から読んでも右から読んでも同じ数字の並びになる数のことです（例：121、12321）。

素数とは、約数が 1 とその数自身のみである数のことです。

入出力例で理解する

入力

N = 12

出力

101

説明

12 より大きい回文数は 22, 33, 44, 55, 66, 77, 88, 99, 101 … と続きます。このうち最初の素数は 101 です。22〜99 はすべて 11 の倍数であるため素数にはなりません。

解法アプローチ

最も単純な方法は、N より大きい回文数を順番に生成し、それぞれが素数かどうかを判定することです。しかし、この方法は非効率です。

より効率的な解法として、「偶数桁の回文数はすべて 11 の倍数である」という数学的性質を利用します。

証明

11 % 11 = 0
1111 % 11 = 0
xyzzyx % 11 = 0

つまり、偶数桁の回文数は必ず 11 で割り切れるため、11 以外の偶数桁の回文数が素数になることはありません。そこで、奇数桁の回文数だけを生成・判定すればよく、探索>すればよく、探索範囲を大幅に絞り込むことができます。

C++ 実装例

#include <iostream>
#include <string>
using namespace std;

bool isPrime(int num) {
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}

int primePalindrome(int N) {
    // 8〜11 の範囲では答えは 11（唯一の2桁の回文素数）
    if (8 <= N && N <= 11)
        return 11;
    // 奇数桁の回文数を生成して判定
    for (int x = 1; x < 100000; ++x) {
        string s = to_string(x), r(s.rbegin(), s.rend());
        int y = stoi(s + r.substr(1));
        if (y >= N && isPrime(y))
            return y;
    }
    return -1;
}

int main() {
    int N = 432;
    cout << "The next prime palindrome is " << primePalindrome(N);
    return 0;
}

出力

The next prime palindrome is 727

コードのポイント

• isPrime 関数： 2 の倍数を先に除外し、奇数のみを試し割りすることで素数判定を高速化しています。
• primePalindrome 関数： 数値 x を文字列化し、反転した文字列と結合することで奇数桁の回文数を効率的に生成します。r.substr(1) を使うことで中央の数字が重複しないようになっています。
• N が 8 以上 11 以下の場合、唯一の 2 桁の回文素数である「11」が答えとなります。

まとめ

偶数桁の回文数が必ず 11 の倍数になるという性質を活用すれば、すべての回文数を調べる代わりに奇数桁の回文数だけを探索でき、計算量を大幅に削減できます。数学的な性質をアルゴリズムに組み込むことで、処理効率が大きく向上する好例といえるでしょう。