C++ 함수를 활용한 소수 판별 프로그램 완벽 가이드

소수(素數)란 1보다 큰 자연수 중에서 약수가 오직 1과 자기 자신뿐인 수를 의미합니다. 즉, 1과 자신 외에는 어떤 수로도 나누어 떨어지지 않는 수입니다.

가장 작은 소수들은 다음과 같습니다.

2, 3, 5, 7, 11, 13, 17

이번 글에서는 함수를 사용하여 특정 숫자가 소수인지 아닌지 판별하는 C++ 프로그램을 살펴보겠습니다.

예제 코드

#include <iostream>
using namespace std;
void isPrime(int n) {
    int i, flag = 0;
    for(i=2; i<=n/2; ++i) {
        if(n%i==0) {
            flag=1;
            break;
        }
    }
    if (flag==0)
    cout<<n<<"은(는) 소수입니다"<<endl;
    else
    cout<<n<<"은(는) 소수가 아닙니다"<<endl;
}
int main() {
    isPrime(17);
    isPrime(20);
    return 0;
}

실행 결과

17은(는) 소수입니다
20은(는) 소수가 아닙니다

코드 동작 원리

위 프로그램의 핵심은 isPrime() 함수입니다. 이 함수는 입력받은 숫자 n이 소수인지 여부를 판단하는 역할을 합니다.

먼저, 함수 내부에는 2부터 n의 절반까지 반복하는 루프가 존재합니다. 이 범위까지만 검사해도 충분한 이유는, n의 절반보다 큰 수로는 절대 나누어 떨어질 수 없기 때문입니다.

루프 안에서 각 값으로 n을 나누어 보고, 나눗셈의 나머지가 0이라면 n이 1과 자기 자신이 아닌 다른 수로 나누어진다는 의미입니다. 따라서 해당 수는 소수가 아니며, flag 변수를 1로 설정한 후 break 문으로 루프를 즉시 탈출하여 불필요한 연산을 줄입니다.

for(i=2; i<=n/2; ++i) {
    if(n%i==0) {
        flag=1;
        break;
    }
}

루프가 종료된 후 flag 값을 확인합니다. flag가 계속 0으로 유지되었다면 중간에 나누어 떨어지는 수가 없었다는 뜻이므로 해당 숫자는 소수입니다. 반대로 flag가 1로 변경되었다면 약수를 발견한 것이므로 소수가 아닙니다.

if (flag==0)
cout<<n<<"은(는) 소수입니다";
else
cout<<n<<"은(는) 소수가 아닙니다";

main() 함수에서의 호출

마지막으로 main() 함수에서 isPrime() 함수를 호출하며 인자로 17과 20을 전달합니다. 그 결과 17은 소수로, 20은 소수가 아닌 것으로 출력됩니다.

isPrime(17);
isPrime(20);

이처럼 함수를 활용하면 소수 판별 로직을 재사용 가능한 형태로 분리할 수 있어 코드의 가독성과 유지보수성이 크게 향상됩니다. 참고로 더 효율적인 구현이 필요하다면 검사 범위를 √n까지 줄이는 방법도 고려할 수 있습니다.