C++での素数の再帰プログラム

入力として整数が与えられます。目標は、再帰を使用して、入力数Numが素数であるか非素数であるかを見つけることです。

数が素数であるかどうかを確認するには、i=2からi<=Num/2までのトラバースを開始します。いずれかのiがNumで完全に割り切れる場合、素数は1とその数自体でしか割り切れないため、その数は素数ではありません。

例

入力 −数値=32

出力 − 32は非プライムです！

説明 − i=2からi<=32/2までトラバースを開始すると、最初は2で完全に割り切れ、非素数であることを示します。

入力 −数値=43

出力 − 43は素数です！

説明 − i=2からi<=43/2までトラバースを開始すると、2から21までの数値で割り切れなくなります。これは素数であることを示しています。

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、入力番号を受け取る再帰関数checkPrime（int num1、int index）と、2からnum1/2までの値をとるインデックスを使用しています。

基本ケースの場合-：num1 <2の場合、プライムではないため1を返します。

num1 ==2の場合、素数であるため2を返します。

それ以外の場合：-if（index <=num1 / 2）の場合、インデックスがnum1を完全に分割しないポイントに到達したため、素数でのみ可能であるため1を返します。それ以外の場合は、result =checkPrime（num1、index+1を使用して次のインデックスに戻ります。 ）

• 入力番号Numを取ります

• 関数checkPrime（int num1、int index）は入力を受け取り、数値が素数の場合は1を返し、それ以外の場合は0を返します。

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

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

• num1％indexが<=num1 / 2の場合、1を最大num1 / 2として返します。num1は完全に分割されていないため、num1は素数です

  。

• result =checkPrime（num1、index + 1）を使用して、次のインデックスを繰り返します。

• 結果を返します。

• メイン内で得られた結果を印刷します。

例

#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!