C++で指定した数以下の最大の特殊素数を求める方法

問題の概要

ある数 n が与えられたとき、n 以下の最大の「特殊素数」を求めることを考えます。特殊素数とは、桁を一つずつ付け加えて構成したとき、その過程で現れるすべての数（先頭からの接頭辞）が素数となる数のことです。

たとえば 379 は、3・37・379 のいずれも素数であるため特殊素数です。一方、途中の数に素数でないものが含まれる数は、特殊素数とはみなされません。

アルゴリズムの考え方

ここではエラトステネスの篩（ふるい）を使用します。まず n までの素数表（篩配列）を作成し、その後、N から順に数を減らしながら以下の手順で判定を行います。

1. その数が素数かどうかを確認する
2. 素数であれば、桁を右から一つずつ取り除いた数もすべて素数かどうか（＝特殊素数かどうか）を確認する
3. 条件を満たす数が見つかった時点で、それが n 以下の最大の特殊素数となる

実装例（C++）

#include<iostream>
using namespace std;
bool isSpecialPrime(bool sieve[], int num) {
    while (num) {
        if (!sieve[num]) {
            return false;
        }
        num /= 10;
    }
    return true;
}
void findSpecialPrime(int N) {
    bool sieve[N + 10];
    for(int i = 0; i<N+10; i++){
        sieve[i] = true;
    }
    sieve[0] = sieve[1] = false;
    for (long long i = 2; i <= N; i++) {
        if (sieve[i]) {
            for (long long j = i * i; j <= N; j += i) {
                sieve[j] = false;
            }
        }
    }
    while (true) {
        if (isSpecialPrime(sieve, N)) {
            cout << N << '\n';
            break;
        }
        else
            N--;
    }
}
int main() {
    cout << "範囲 (2 -> 400) の特殊素数: ";
    findSpecialPrime(400);
    cout << "範囲 (2 -> 100) の特殊素数: ";
    findSpecialPrime(100);
}

出力結果

範囲 (2 -> 400) の特殊素数: 379
範囲 (2 -> 100) の特殊素数: 79

コードの解説

isSpecialPrime 関数

篩配列と判定対象の数を受け取り、数を 10 で割りながら末尾の桁を順に取り除き、各段階の数が素数かどうかを確認します。途中で素数でない数が現れた時点で false を返し、すべての接頭辞が素数であれば true を返します。

findSpecialPrime 関数

まずエラトステネスの篩を用いて N 以下の素数表を作成します。その後、N から降順に数を調べ、最初に見つかった特殊素数を出力して終了します。降順に探索するため、最初に見つかった値が必ず最大の特殊素数になります。

計算量と実装上の注意点

エラトステネスの篩による素数表の作成は O(N log log N) で行え、特殊素数の探索は素数同士の間隔が比較的狭いため実用上高速に動作します。なお、サンプルコードでは可変長配列（VLA）を使用していますが、これは標準 C++ の機能ではないため、移植性を重視する場合は std::vector<bool> の利用を検討するとよいでしょう。