[C언어] : 에라토스테네스의 체

에라토스테네스의 체

• 알고리즘을 배우다 보면 빠질 수 없는 부분이 에라토스테네스의 체다.체로 치듯이 수를 걸러낸다고 해서 '에라토스테네스의 체'라고 부른다.
• 노다가성이 즐비하지만 특정 범위 내의 소수를 판정하는데 효율적이다.

1. 일단 1부터 100까지의 숫자를 쭉 쓴다.
2. 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.
3. 2를 제외한 2의 배수를 제거한다.
4. 3를 제외한 3의 배수를 제거한다.
5. 5의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다.)
6. 2,3 다음으로 남아있는 가장 작은 소수, 5를 제외한 5의 배수를 제거해야 한다.
7. 마지막으로 7을 제외한 7의 배수까지 제거한다.

예제를 보자.

만약에 1~300까지의 소수를 구해라 어떻게 할 것인가?

<전체 코드>

#include <stdio.h>
#include <math.h>

#define SIZE 120

int main(void)
{
    int a[SIZE] = { 0 };	// 0 ~ 300
    int i, j;

    for (i = 2; i <= sqrt(SIZE); i++) {	// 최대값의 제곱근까지 반복
        if (a[i] == 0) {		
            for (j = 2; i * j < SIZE; j++) {	// 자신을 제외한 i의 배수 제거
                a[i * j] = 1;
            }
        }
    }

    for (i = 2; i < SIZE; i++) {
        if (a[i] == 0) printf("%d\n", i);
    }

    return 0;
}

• 11^2 > 120이기 때문에 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2,3,5,7의 배수를 지우고 남는 수는 소수다.

핵심 코드는 2개다.

<코드 1>

for (i = 2; i <= sqrt(SIZE); i++) {	// 최대값의 제곱근까지 반복
        if (a[i] == 0) {		
            for (j = 2; i * j < SIZE; j++) {	// 자신을 제외한 i의 배수 제거
                a[i * j] = 1;
            }
        }
    }

• i=2부터 쭉 돌면서 a[i] == 0이면 ->
  2(i) x 3(j)
  2(i) x 4(j)
  2(i) x 5(j)
  2(i) x 6(j)등 자신을 제외한 i의 배수를 제거한다.(1로 표현)

<코드 2>

    for (i = 2; i < SIZE; i++) {
        if (a[i] == 0) printf("%d\n", i);
    }

    return 0;
}

• a[i] == 0 값을 가질 때, 그 인덱스 값을 출력한다.