【C++】再帰を使って素数を判定するプログラムの作り方

整数が入力として与えられたとき、その入力値 Num が素数か非素数かを再帰（リカーション）を使って判定するのが本記事の目的です。

ある数が素数かどうかを調べるには、i = 2 から i <= Num/2 の範囲を順番に確認していきます。この範囲内のどれかの i で割り切れた場合、その数は素数ではありません。素数は 1 とその数自身でしか割り切れないためです。

例

入力 − Num = 32

出力 − 32 is non-Prime!（32は素数ではない）

説明 − i = 2 から i <= 32/2 の範囲で確認すると、最初の時点で 2 で割り切れてしまうため、素数ではないとわかります。

入力 − Num = 43

出力 − 43 is a Prime number!（43は素数）

説明 − i = 2 から i <= 43/2 の範囲で確認しても、2〜21 のどの数でも割り切れないため、素数であることがわかります。

プログラムで使用するアプローチ

このアプローチでは、入力された数値と、2 から num1/2 までの値を取るインデックスを受け取る再帰関数 checkPrime(int num1, int index) を使用します。

基本ケース（ベースケース）

• num1 < 2 の場合は 0 を返します。2 未満の数は素数ではないためです。

• num1 が 2 または 3 の場合は 1 を返します。2 と 3 は素数であるためです。

• num1 % index == 0 の場合は 0 を返します。index で割り切れるということは素数ではないことを意味します。

• index が num1/2 を超えた場合は 1 を返します。num1/2 までのどの数でも num1 を割り切れなかったということで、これは素数の場合にのみ起こり得ます。

再帰ケース

• index <= num1/2 の間は、result = checkPrime(num1, index + 1) として次のインデックスで再帰的に呼び出します。

• 最終的な result を呼び出し元に返します。

• main 関数内で取得した結果を出力します。

処理の流れ

• 入力として数値 Num を受け取る

• 関数 checkPrime(int num1, int index) が引数を受け取り、素数なら 1、そうでなければ 0 を返す

• main 関数の中で結果を判定して表示する

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int checkPrime(int num1, int index){
    if(num1<2){
        return 0;
    }
    if (num1 == 2 || num1==3){
        return 1;
    }
    if (num1 % index == 0){
        return 0;
    }
    if (index >= num1/2){
        return 1;
    }
    int result=checkPrime(num1, index+1);

    return (result);
}
int main(){
    int Num = 31;
    if (checkPrime(Num,2)==1){
        cout <<Num<<" is a Prime number !";
    }
    else{
        cout <<Num<<" is non Prime!";
    }

    return 0;
}

出力

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

31 is a Prime number!