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!

以上是 C++质数递归程序 的全部内容, 来源链接: utcz.com/z/355832.html

回到顶部