C++でNより大きい最小の素数回文を求めるアルゴリズムと実装

整数 N が与えられたとき、N より大きい最小の素数回文を求めるのがこの記事のテーマです。素数回文（Prime Palindrome）とは、素数であり、かつ回文（前から読んでも後ろから読んでも同じ並びになる数）でもある数のことです。まずは具体例を見てみましょう。

入力

N = 10

出力

11

10 の次の素数は 11 ですが、11 は「1・1」と前後どちらから読んでも同じ数、つまり回文でもあるため、答えは 11 になります。

アルゴリズム

• 基準となる数値 N を初期化します。

• 与えられた数が素数かどうかを判定する関数 isPrime を用意します。

• 与えられた数が回文かどうかを判定する関数 isPalindrome を用意します。

• N + 1 から順に候補の数を 1 ずつ増やしながら調べ、素数かつ回文である数が見つかった時点でその値を返します。

C++での実装

以下が、上記アルゴリズムを C++ で実装した例です。

#include <bits/stdc++.h>
using namespace std;

// 素数判定：√n までの数で割り切れるかを確認
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 回文判定：数値を反転して元の数と比較
bool isPalindrome(int n) {
    int num = n, digit, rev = 0;
    while (num) {
        digit = num % 10;
        rev = (rev * 10) + digit;
        num /= 10;
    }
    return n == rev;
}

// Nより大きい最小の素数回文を返す
int getNextSmallestPrimePalindrome(int n) {
    int i = n + 1;
    while (true) {
        if (isPrime(i) && isPalindrome(i)) {
            return i;
        }
        i += 1;
    }
}

int main() {
    int N = 15;
    cout << getNextSmallestPrimePalindrome(N) << endl;
    return 0;
}

出力

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

101

N = 15 の場合は少し注意が必要です。17 や 19 は素数ですが回文ではないため候補外となり、22 や 33 のような偶数桁の回文はすべて 11 の倍数になるため素数にはなりません。そのため、素数かつ回文を同時に満たす最初の数は 101 となります。

探索を高速化するポイント

単純な全探索でも正しい答えは得られますが、N が大きくなると処理に時間がかかります。次のような工夫で効率化できます。

• 偶数桁の回文をスキップする： 偶数桁の回文（11 以外）は必ず 11 の倍数になるため素数ではありません。奇数桁の回文だけを生成して判定すれば、無駄な探索を大幅に減らせます。

• 素数判定の計算量を意識する： 素数判定は 2 から √n まで試し割りできれば十分で、O(√n) で判定できます。