에라토스테네스의 체 - C언어

에라토스테네스의 체는 소수(Prime Number)를 찾는 방법이다.

알고리즘

1. 소수를 찾을 범위(최대값)를 결정한다.
2. 2부터 최대값까지 모든 수를 나열한다.
3. 2는 소수이므로 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남은 수 중 3은 소수이므로 자신을 제외한 3의 배수를 모두 지운다.
5. 남은 수 중 5는 소수이므로 자신을 제외한 5의 배수를 모두 지운다. (4는 2의 배수이므로 지워짐)
6. 남은 수 중 7은 소수이므로 자신을 제외한 7의 배수를 모두 지운다. (6은 2의 배수이므로 지워짐)
7. 위의 과정을 최대값의 제곱근까지만 반복하면 소수만 남는다.

ex)
200 이하의 소수를 구하고 싶다면, 15^2 > 200 이므로 15보다 작은 수의 배수들만 지우면 된다.
-> 200보다 작거나 같은 수 중에서 2, 3, 5, 7, 11, 13의 배수(자기 자신 제외)를 지우고 남는 수는 모두 소수

구현

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

#define SIZE 201

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

    for(i = 2; i <= sqrt(SIZE); i++) {	// 최대값의 제곱근까지 반복
        if(a[i] == 0) {		//i가 소수이면
            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;
}