‘에라토스테네스의 체’에 관한 위키백과 문서를 참고해 소수(prime numbers) 구하기 프로그램을 C로 작성해보았다.

인덱스(index) 값이 0부터 100까지 있는 배열에서 합성수들은 FALSE처리하여 걸러내고 소수는 TRUE처리한다. 나중에 TRUE 마킹을 한 인덱스(index)들만 반복문을 돌려 출력해준다.

for문이 3개고 그 중 하나가 이중 for문이라는 것에 아쉬움이 남는다.

#include <stdio.h>

#define TRUE 1
#define FALSE 0

void eratos_sieve(const int MAX)
{
    int arr[MAX+1];
    int i, j, cnt;

    // Fill `arr` with TRUEs
    for(i=0; i<=MAX; i++)
        arr[i] = TRUE;

    // Mark non-prime numbers with FALSE
    arr[0] = FALSE;
    arr[1] = FALSE;
    for(i=2; i<=MAX; i++)
    {
        if(arr[i] == FALSE)
            continue;
        arr[i] = TRUE;
        for(j=2; i*j<=MAX; j++)
            arr[i*j] = FALSE;
    }

    // Print first 10 numbers in the array cells marked TRUE
    for(i=0, cnt=1; cnt<=10 && i<=MAX; i++)
    {
        if(arr[i])
        {
            printf("%d ", i);
            cnt++;
        }
    }
    puts("");
}

int main()
{
    eratos_sieve(100);
    return 0;
}