입력으로 정수가 주어집니다. 목표는 재귀를 사용하여 입력 숫자 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 사이의 어떤 수로도 나눌 수 없습니다. 이는 소수임을 알려줍니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 2에서 num1/2까지의 값을 취하는 입력 숫자와 인덱스를 취하는 재귀 함수 checkPrime(int num1, int index)를 사용하고 있습니다.
기본 경우-:num1<2이면 소수가 아니므로 1을 반환합니다.
num1==2이면 2를 소수로 반환합니다.
Else:- 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이면 2와 3이 소수이므로 1을 반환합니다.
-
num1%index가 <=num1/2이면 num1/2까지 1을 반환합니다.
-
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!