[Algorithm] 에라스토테네스의 체 : 소수 구하기

#에라스토테네스의 체

에라스토테네스의 체란 일정 범위 내의 소수를 찾는 가장 효율적인 알고리즘이다.

알고리즘의 원리는 어떤 수의 배수는 소수가 될 수 없다는 원리에 착안하여, 어떤 수의 배수가 되는 수들을 지워나가는 식이다. 

 

1. 2 ~ N 까지의 자연수 중 먼저 소수를 찾는다(해당 범위에서는 2부터 시작됨)

2. 그 소수(2)를 제외한, 나머지 N까지의 수 중 우리가 찾은 소수(2)의 배수들을 모두 지운다.

3. 다음 소수(3)를 찾고 이 수를 제외한, 나머지 N까지의 수 중 방금 우리가 찾은 소수(3)의 배수들을 모두 지운다.

4. 위 과정을 N의 제곱근까지 반복한다(소수점은 내림한다).

 

해당 과정을 반복하고나면, 지워지고 남은 수들이 모두 소수가 된다.

---

#구현

#include <stdio.h>
#include <math.h>
#define SIZE 200

int main()
{
    int ary[SIZE] = {0}; // 일단 다 0(소수)으로 초기화.
    int i, j;
    for(i=2; i<=sqrt(SIZE); i++){ // 제곱근 까지만 반복하면 됨.
        if(ary[i] == 0){ // 만약 ary[i]가 소수이면,
            for(j=i*2; j<SIZE; j=j+i){ 
                ary[j] = 1; // 해당 소수를 제외한, 그 소수의 배수들을 모조리 1(합성수)로 초기화한다.
            }
        }
    }

    for(i=2; i<SIZE; i++){
        if(ary[i] == 0){ // 소수이면 출력한다
            printf("%d ", i);
        }
    }

    return 0;
}