C언어, 소수 판별하기

소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 수를 말합니다. 

즉, 약수가 2개만 존재하는 것입니다.

2, 3, 5, 7, 11, 13, ... 이렇게 다양한 수가 있습니다. 

0은 1로도 못 나누기 때문에 소수가 아니고, 1은 약수가 2개가 아니죠.

 

그렇다면 소수를 판별해 주는 함수를 만들어 보도록 하겠습니다. 

 

int    OdOp_is_prime(int nb)
{
    int    i;

    if (nb < 2)
        return (0);
    i = 2;
    while (nb % i != 0 && i <= nb / 2)
    {
        i++;
    }
    if (i > nb / 2)
        return (1);
    return (0);
}

앞에서도 설명했다시피 만약 입력받은 수가 2보다 작다면 소수가 아닌 것이기 때문에 0을 리턴해 줍니다. 

 

이제 nb를 i로 나누어줍니다. 이때 나머지가 0이 나오지 않다면 i를 1을 증가시킵니다. 

여기서 while문을 종료하는 2가지 경우가 있습니다.

첫 번째로 nb가 i로 나누어 떨어질 때이고, 두 번째는 i가 nb / 2보다 커졌을 때입니다. 

첫 번째는 이해가 되시겠지만 두 번째는 이해가 되시지 않을 것입니다. 

예를 한 가지 들어보겠습니다. 

16의 약수는 1, 2, 4, 8, 16입니다. 

15의 약수는 1, 3, 5, 15입니다. 

여기서 두 수의 약수에서 1과 자기 자신의 수를 빼보도록 하겠습니다. 

16은 2, 4, 8이고

15는 3, 5입니다. 

즉, 무조건 nb / 2보다 작습니다.

 

그렇다면 첫 번째의 경우로 즉, 나누어 떨어지는 수가 발견이 되어 while문이 종료가 된다면 1을 출력하여 nb가 소수임을 알려줍니다. 

두 번째의 경우로 즉, i가 nb / 2보다 커졌기 때문에 while문이 종료된다면 소수가 아니기 때문에 0을 출력합니다. 

 

이렇게 소수를 판별하는 알고리즘을 만들어 보았습니다. 

이번 포스팅이 여러분의 궁금증을 많이 해소시켜 주었으면 좋겠습니다.