[소수 판별법]에라토스테네스의 체

에라토스테네스의 체

 소수란??

 소수(Prime Number) 는 약수로 1과 자기 자신만을 가지는 수이다. 단 1은 소수가 아니다.

 에라토스테네스의 체

 이름 그대로 에라토스테네스가 고안했다고 여겨지는 소수 판정 방법이다. 방법에 대해서 말하자면 2부터 (1은 소수가 아니므로) 차례대로 검색을 하는데 검색을 할때 소수를 발견할 시 그 소수의 배수를 체크를 하는 것이다. 그렇다면 그 이후의 발견되는 숫자들 중 체크가 되지 않는 수들은 약수로 1과 자기 자신만을 가지는 성질을 가지는 소수인것이다. 

<위키백과에 있는 이미지를 가져왔습니다.>

  위의 예시는 1부터 120에 해당하는 숫자의 소수를 판별하는 방법입니다. 여기서는 121(121>120)의 제곱근인 11까지 검색해도 충분합니다. 그 후 남는 숫자들이 소수가 된다.

예제

  1 ~ 100까지 소수를 구하는 알고리즘 입니다.

#include <stdio.h>
int numbers[110];
 
 
int main(void){
 
    
    int prinumber[110];
    int prinumbersize = 0;
    for (int i = 2; i <= 100; i++)
    {
        if (numbers[i] == 0)
        {
            int count = 0;
            prinumber[prinumbersize++] = i;
            while (count++*i <= 100)
                numbers[count*i] = 1;
            
        }
    }
 
    for (int i = 0; i < prinumbersize; i++)
        printf("%d ", prinumber[i]);
 
    printf("\n");
 
    return 0;
 
}