정수 하나가 입력으로 주어졌을 때, 재귀(recursion)를 이용하여 해당 숫자가 소수인지 아닌지 판별하는 것이 목표입니다.
어떤 수가 소수인지 확인하려면 i=2부터 i<=Num/2까지 차례대로 검사합니다. 이 범위에서 Num을 나누어 떨어지게 하는 값이 하나라도 존재한다면 그 수는 소수가 아닙니다. 소수는 1과 자기 자신으로만 나누어 떨어지는 수이기 때문입니다.
예제
입력 − Num = 32
출력 − 32은(는) 소수가 아닙니다!
설명 − i=2부터 i<=32/2까지 검사하면, 가장 먼저 32가 2로 나누어 떨어지므로 소수가 아니라고 판단할 수 있습니다.
입력 − Num = 43
출력 − 43은(는) 소수입니다!
설명 − i=2부터 i<=43/2까지 검사해도 2와 21 사이의 어떤 수로도 나누어 떨어지지 않으므로 소수임을 알 수 있습니다.
알고리즘 접근 방식
이 방법에서는 입력받은 숫자와 인덱스(index)를 매개변수로 받는 재귀 함수 checkPrime(int num1, int index)를 사용합니다. 인덱스는 2부터 num1/2까지의 값을 가집니다.
재귀 함수의 동작 과정은 다음과 같습니다.
기저 사례 1: num1 < 2이면 0을 반환합니다. 2보다 작은 수는 소수가 아닙니다.
기저 사례 2: num1이 2 또는 3이면 1을 반환합니다. 2와 3은 소수입니다.
나눗셈 검사: num1 % index == 0이면 0을 반환합니다. index로 나누어 떨어진다는 것은 약수가 존재한다는 의미이므로 소수가 아닙니다.
종료 조건: index가 num1/2보다 커질 때까지 나누어 떨어지는 경우가 없었다면 1을 반환합니다. num1/2까지만 검사해도 충분한 이유는, 어떤 수의 약수 중 자기 자신을 제외한 가장 큰 약수는 항상 num1/2 이하이기 때문입니다.
재귀 호출: 위 조건에 해당하지 않으면 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<<" is a Prime number !";
}
else{
cout <<Num<<" is non Prime!";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
31 is a Prime number!