I wannabe FALCON

입력된 양의 정수가 소수인지 아닌지를 확인해보려 합니다. 우선, 소수가 무엇인지부터 알아야겠죠? 소수란 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 말합니다.

그렇다면 알고리즘도 이러한 소수의 특징을 이용하여 구현할 수 있습니다. 입력된 값이 1보다 크고 자기 자신보다 작은 자연수에 의해 나누어 떨어지는지만 확인하면 되죠. 여기서 반복문을 사용해야 한다는 것을 짐작하시겠죠?

이제 소스를 보겠습니다.

#include <stdio.h>

int check(unsigned int);

int main(void)
{
    unsigned int number = 1;

    printf("양의 정수를 입력하면 소수인지 알려줄게. : ");
    scanf("%d", &number);

    if(check(number)) printf("이 수는 소수입니다. \n");
    else printf("이 수는 소수가 아닙니다. \n");

    return 0;
}

자연수에 한해서만 연산하면 되므로 int보다 최대값이 더 큰 unsigned으로 변수 number를 선언하였습니다. 그리고 scanf() 함수로 값을 입력받아 check() 함수로 넘깁니다. 이 check() 함수에서 위에 얘기했던 소수의 특성을 이용하여 알고리즘을 구현할 것입니다.

int check(unsigned int number)
{
    unsigned int div;

    for(div = 2; number % div; div++);
    if(div == number) return 1;
    else return 0;
}

넘겨받은 number를 나눠줄 변수 div를 선언합니다. number와 같은 범위를 가져야 하므로 unsigned int로 선언되었습니다.

역시 반복문을 이용하는데요. 의외인 게 반복문 안에 어떠한 문장도 없습니다. 반복문 그 자체로 끝나죠. 이건 div를 이용하기 때문입니다. 반복문의 조건문항을 보면 number를 div로 나누어 남은 나머지라 되어 있습니다. 나누어 떨어지면 0이, 그렇지 않으면 어떠한 수가 결과로 나오죠. C에서 0은 false를 의미하고 그 외의 수는 true를 의미합니다. 즉, 나누어 떨어져 0이 나오면 반복문을 중지하라는 뜻입니다.

이렇게 반복문이 중지되고나서 div에 어떠한 값이 저장되어 있을겁니다. 그 값이 number와 같다면, 그러니까 결국 1과 자기 자신을 제외한 약수가 존재하지 않다는 것이 확인된다면, true를 의미하는 1을 반환합니다.

반환된 값은 main() 함수의 조건문에서 사용되어 결과를 출력하게 됩니다.

소수인지 아닌지를 확인하는 간단한 알고리즘이었습니다. 하지만 이 알고리즘은 수가 커질수록 연산이 길어지는 단점이 있습니다. 소스가 간단하니 뭘 바라겠어요?

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

6l4ck3y3 0x07 알고리즘 C, Programming, 반복문, 소수, 알고리즘