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 返回 0，因为小于 2 的数字是非质数。

• 如果 num1 是 2 或 3，则返回 1，因为 2 和 3 是素数。

• 如果 num1%index <= num1/2 然后返回 1 作为高达 num1/2 没有数字完全划分 num1 所以 num1 是素数

• 使用 result=checkPrime(num1, index+1) 递归获取下一个索引。

• 返回结果。

• 打印在 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<<" 是素数！";
   }
   else{
      cout <<Num<<" 不是素数！";
   }

   return 0;
}

如果我们运行上面的代码，它将生成以下输出

31 is a Prime number!