C++で数値が完全素数（フルプライム）かどうかを判定する方法

完全素数（フルプライム）とは？

本記事では、ある数値が「完全素数（フルプライム）」であるかどうかを判定する方法を解説します。完全素数とは、その数値自体が素数であり、かつ各桁の数字もすべて素数である数のことです。例えば、37は2桁とも素数の数字（3と7）で構成され、数値全体も素数であるため、完全素数です。一方、97は数値自体は素数ですが、各桁に9という素数でない数字が含まれているため、完全素数ではありません。

判定のアプローチ

効率的な判定方法は以下の2段階で行います。

まず、素数でない桁が含まれていないかを確認します。各桁の数字は0から9の範囲に収まるため、この範囲で素数となるのは2、3、5、7の4つだけで、それ以外の数字（0、1、4、6、8、9）はすべて素数ではありません。すべての桁が素数であれば、次に数値全体が素数であるかどうかを判定します。この順序で処理することで、桁のチェックが失敗した時点で素数判定の計算を省略でき、無駄な計算を避けられます。

C++による実装例

#include <iostream>
using namespace std;

// 数値が素数かどうかを判定する関数
bool isPrime(int n){
    for(int i = 2; i <= n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

// すべての桁が素数（2, 3, 5, 7）かどうかを判定する関数
bool isDigitPrime(int n) {
    int temp = n, digit;
    while(temp){
        digit = temp % 10;
        if(digit != 2 && digit != 3 && digit != 5 && digit != 7){
            return false;
        }
        temp = temp / 10;
    }
    return true;
}

// 完全系数かどうかを判定する関数
bool isFullPrime(int n){
    return (isDigitPrime(n) && isPrime(n));
}

int main() {
    int num = 37;
    if(isFullPrime(num)){
        cout << "The number is Full Prime";
    } else {
        cout << "The number is not Full Prime";
    }
}

実行結果

The number is Full Prime

コードの解説

isPrime関数は、2からn/2までの整数で順に割り切れるかを調べるシンプルな試し割り法です。割り切れる数が存在すれば素数ではないと判定します。

isDigitPrime関数は、数値を10で割った余りを取り下位の桁から順に確認し、桁の数字が2、3、5、7のいずれでもない場合にfalseを返します。

isFullPrime関数は、この2つの関数を組み合わせ、桁のチェックと素数判定が両方ともtrueの場合にのみtrueを返します。なお、桁がすべて素数である数値は必ず2以上になるため、この実装でも1や0を正しく「完全素数ではない」と判定できます。

計算量は、桁のチェックがO(d)（dは桁数）、素数判定がO(n)となるため、全体としてはO(n)で処理されます。より大きな数値を扱う場合は、平方根まで試し割りを行う方法や、エラトステネスの篩を活用することでさらに高速化できます。