C++로 숫자가 소수인지 확인하는 프로그램 작성법

소수(Prime Number)란 1보다 큰 정수 중에서 약수가 오직 1과 자기 자신뿐인 수를 의미합니다. 가장 처음 등장하는 소수들은 다음과 같습니다.

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

이번 글에서는 C++를 이용해 주어진 숫자가 소수인지 아닌지 판별하는 프로그램을 살펴보겠습니다.

예제 코드

#include <iostream>
using namespace std;
int main() {
    int n=17, i, flag = 0;
    for(i=2; i<=n/2; ++i) {
        if(n%i==0) {
            flag=1;
            break;
        }
    }
    if (flag==0)
    cout<<n<<" is a prime number";
    else
    cout<<n<<" is not a prime number";
    return 0;
}

실행 결과

17 is a prime number

코드 동작 원리

위 프로그램의 핵심은 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 값에 따라 결과를 출력합니다. flag가 계속 0으로 유지되었다면 어떤 수로도 나누어지지 않았다는 의미이므로 해당 숫자는 소수입니다. 반대로 flag가 1로 변경되었다면 약수를 발견한 것이므로 소수가 아니라고 출력됩니다.

if (flag==0)
cout<<n<<" is a prime number";
else
cout<<n<<" is not a prime number";

추가 팁: 더 효율적인 방법

실제로는 n/2까지만 검사하는 것보다 √n(제곱근)까지만 검사해도 충분합니다. n의 약수는 항상 √n 이하의 값과 짝을 이루기 때문입니다. 예를 들어 i*i <= n 조건을 사용하면 큰 숫자를 판별할 때 연산 횟수를 크게 줄일 수 있어 성능이 향상됩니다.