数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++递归实现素数判断
给定一个整数作为输入。目标是使用递归方法判断输入数字Num是否为素数。
要检查一个数字是否为素数，从i=2遍历到i<=Num/2。如果任何i都能被Num整除，则该数字不是素数，因为素数只能被1和自身整除。
示例
输入 − Num = 32
输出 − 32不是素数！
说明 − 如果我们从i=2遍历到i<=32/2，那么首先它将被2整除，这表明它不是素数。
输入 − Num = 43
输出 − 43是素数！
说明 − 如果我们从i=2遍历到i<=43/2，那么它将不会被2到21之间的任何数字整除。这表明它是素数。
下面程序中使用的方法如下
在这种方法中，我们使用递归函数checkPrime(int num1, int index)，它接收输入数字和索引，索引的值将从2到num1/2。
对于基本情况：如果num1<2，则返回1，因为它不是素数。
如果num1==2，则返回2，因为它是一个素数。
否则：如果(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)递归调用下一个索引。
返回result。
在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!
更新于： 2021年11月2日
6K+ 次浏览
广告