요즘 어딘가의 나사가 풀려 버린 것만 같아
나름대로 어떻게 정신통일을 해볼까, 하다가
기본적인 알고리즘 공부를 해보자! ... 라는 결심을 하게 되었습니다. -_;;

마침 한빛미디어에서 출판된 책도 학교 도서관에서 빌렸고,
여차 저차해서 최근 열독중입니다. (일본인 저자가 지은 『C언어로 배우는 알고리즘 입문』)
인동형님께서 사주신 C++ 책도 간간히 보고 있는데 어쨌든 중요한 점은
제가 알고리즘이나 수리적 추론 능력이 완전 저질급이었다는 점입니다. ㅠ.ㅠ;;

그래서...
앞으로 간간히 [뻘쭘한 알고리즘] 이라는 걸로다가
책을 보면서 나름 재밌는 알고리즘에 대해 소개를 드릴까 합니다.
오늘은 그 첫 시간으로, 소수 판별을 하는 코드와 특정 범위 내에서의
소수 판별, 그리고 계산량을 줄여서 최적화를 할 수 있는
에라토스테네스의 체 라는, 다소 수학 매니아틱한 뻘글을 소개하겠습니다.

아, 같이 해보실 분들은 자신의 PC 에 C 컴파일러만 설치하시면
쉽게 하실 수 있으실 겁니다. 소스코드는 모두 그대로 쓰실 수 있도록
글 중간 중간에 넣어두겠습니다. 저는 Windows 환경에서 Dev-C++ 이라는
IDE 로 작성을 했는데요, Linux 의 경우 gcc 와 vi 만으로도 훌륭한 개발환경이
됩니다. ^^;;

upload image
(이클립스에서 작업을 할까 했지만, MinGW 와의 연동을 하려다 귀찮아져서... -_;;; )

자, 먼저 오늘 고찰해 볼 소수가 무엇인지 한 번 알아봅시다.
사실은 이미 다들 알고 계시지만, 수학에 아픈 추억을 가지고 있는
저와 같은 분들은 잊어버렸거나 기억에서 지웠을 수도 있습니다.

소수란 자기 자신 외에는 약수를 가지지 않는 수를 말합니다.
2 이상의 양수에 해당하며 2, 3, 5, 7, 11 ... 등의 수를 소수라고 합니다.
(약수란 말은 어떤 수를 나누었을 때 나머지가 0 인 수를 말합니다.)

수학 문제중에보면 500 이하의 숫자 중에서 소수는 몇 개가 있는가?
...같은, 보는 것만으로도 짜증이 치솟는 문제들이 있습니다. (나름 수학 울렁증)
손으로 일일이 계산한다는 것은 굉장히 어려운 일이고, 또 귀찮은 일입니다.
사람은 누구나 귀찮은 일을 싫어합니다. 그래서 수학자들은 그 것을 수학적
추론과 논증을 통해 간략화 하려 하고, 저 같이 게으른 공돌이는 컴퓨터에게
시켜놓고 낮잠을 즐기죠. -_ㅠ;

우리는 오늘, 컴퓨터가 소수를 구해 놓을 수 있도록 일련의 코드를 작성해
컴퓨터에게 전달할 것입니다. 우선 소수인지 아닌지 검사해주는 코드가
실제 실행될 때의 모습을 한 번 보시죠.

upload image
(굉장히 친절한 우리의 소수판별군)

소수를 좀 더 쉽고 빠르게 판별하기 위해서는 몇가지 알아둬야 하는 게 있습니다.
  1. 입력한 수 n 이 n 이외의 정수로 나눠서 떨어지면 그 수는 소수가 아닙니다.
  2. 수학자들의 증명에 의해, n 대신에 root n 부터 위 1의 과정을 거쳐도 결과는 동일합니다.
  3. 루프를 돌면서 어떤 수에 나눠떨어지면 루프를 탈출해 소수가 아님을 알 수 있습니다.
제가 실제로 컴파일 시 사용한 코드는 아래와 같습니다.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* 이 소스코드는 입력받은 숫자가 소수인지 아닌지를 판별하는
역할을 한다. Dev-C++ 에서 작성되었음. */

int main(int argc, char *argv[])
{
    int i, n, limit, stop;
 
    // 루프를 돌면서 숫자를 받자
    while(1) {
        
        // 입력받기
        printf("소수 여부를 판별할 숫자(2 이상의 양수) 입력: ");
        scanf("%d", &n);

        // 유효범위 테스트
        if(n < 2 || n > 100000) {
            printf("너무 큰 숫자이거나 혹은 숫자가 아닙니다!￦n");
            continue;
        }

        // 입력받은 수에 루트를 씌운 값으로 나눠서 소수 여부를 판별해도 된다.
        // 이건 수학자들이 밝혀낸 것임. 일단 루트 씌운 값부터 알아내서 정수형으로 저장하자.
        limit = (int)sqrt(n);

        // 루트씌운 값부터 마이너스를 계속 하면서 루프를 돈다.
        // 만약 소수라면, 그 루트씌운 값 (limit) 이 1이 될 때까지 한번도 나눠서 0 이 되는 일은
        // 없을 것이다. 아니라면, 도중에 탈출하게 된다.
        for(i=limit; i>1; i--) {
            if(n % i == 0)
                break;
        }

        // 위의 루프를 끝까지 돌면서 도중하차 하지 않은 경우가 소수인 경우다.
        if(i == 1)
            printf("%d 는 소수였습니다!￦n", n);
        else
            printf("%d 는 소수가 아닙니다! %d 로 나눠지던걸요?￦n", n, i);

        // 그만할 건지 물어본다.
        printf("￦n￦n그만하실래요? (0 : 그만할래요. / 1 : 계속할거야) ");
        scanf("%d", &stop);

        // 그만한다면 나간다.
        if(stop == 0)
            break;

    }
 
    // 종료 처리
    //system("PAUSE");    
    return 0;
}


주석을 좀 더 보강해 보았는데요, 아마 읽어보시면 쉽게 아실 수 있을 겁니다. ^^;;

위에 제가 작성한 코드에서 좀 더 보강할 점은 입력값에 대한 유효성 검사와
반복 구문입니다. 물론 컴퓨터는 반복문을 눈부신 속도로 처리합니다만,
그 것도 범위가 작을 때 말이지 커지면 커질수록 현격히 느려지게 됩니다.
따라서 반복문을 안 쓰는 방법은 없는지도 고찰해 볼 필요가 있습니다.

위의 코드는 비교적 단순합니다.
숫자를 입력 받고, 그 숫자의 root 씌운 값 (sqrt 함수를 통과한 값) 에 정수부분만
떼어서 그 숫자를 기준으로 나누기를 합니다. 만약 9 가 입력되었다면 root 값은 3이므로
9 을 3 으로 나눠서 떨어지는지 보고 (물론 떨어지므로 소수가 아니죠!) 2 로 나눠서
떨어지는지 보고... 이런식으로 동작하게 됩니다.

이런;;
다시 또 은근슬쩍 스크롤 압박이 재게되는 것 같아 할 수 없이 제목에 (1) 을 붙여놓고
다음 포스트에서 이어 가도록 하겠습니다. (이래 놓고 안 쓸 꺼면서... -_;; )