C++で数値の桁の再帰的な合計が素数かどうかを判定する方法

整数変数 number を入力として受け取り、その各桁の合計を計算して、合計値が素数かどうかを判定する問題について解説します。この処理は、桁の合計が一桁になるまで繰り返され、最終的に得られた一桁の数値が素数であるかどうかを確認します。たとえば、入力が 123 の場合、桁の合計は 1+2+3=6 となり、6 は素数ではないため、結果は「素数ではない」となります。

入出力シナリオの例

入力 − number = 12341

出力 − 桁の再帰的な合計は素数(PRIME)

説明 −

1+2+3+4+1 = 11
1+1 = 2
2 は素数です。

入力 − number = 1664

出力 − 桁の再帰的な合計は素数ではない(NOT PRIME)

説明 −

1+6+6+4 = 17
1+7 = 8
8 は素数ではありません。

アルゴリズムのアプローチ

このプログラムでは、「デジタルルート(digital root)」という数学的な性質を利用しています。ある数の各桁の合計を一桁になるまで繰り返し計算すると、その結果は元の数を 9 で割った余りに等しくなります(ただし、余りが 0 の場合は 9 となります)。したがって、sum 関数では number % 9 を使うことで、実際に桁を順番に足し合わせることなく、一桁の結果を高速に求めることができます。また、一桁の素数は 2、3、5、7 のみなので、これらのいずれかに一致するかどうかを判定するだけで十分です。

• 整数変数 number を宣言します。

• データを関数 Recursively_Prime(number) に渡します。

• 関数 Recursively_Prime(number) の内部:

  • number に関数 sum(number) の戻り値を設定します。

  • number が 2、3、5、7 のいずれかであれば「PRIME」を出力します。

  • それ以外の場合は「NOT PRIME」を出力します。

• 関数 sum(int number) の内部:

  • number が 0 であれば 0 を返します。

  • それ以外で、number % 9 が 0 であれば 9 を返します。

  • それ以外の場合は number % 9 を返します。

• 結果を出力します。

コード例

#include<iostream>
using namespace std;
int sum(int number){
    if(number == 0){
        return 0;
    }
    else{
        if(number % 9 == 0){
            return 9;
        }
        else{
            return number % 9;
        }
    }
}
void Recursively_Prime(int number){
    number = sum(number);
    cout<<"Recursive sum of digits of a number is ";
    if(number == 2 || number == 3 || number == 5 || number == 7){
        cout << "PRIME";
    }
    else{
        cout << "NOT PRIME";
    }
}
int main(){
    int number = 5555;
    Recursively_Prime(number);
}

出力

上記のコードを実行すると、次のような出力が得られます。

Recursive sum of digits of a number is PRIME