[C] 에라토스테네스의 체, 소수 구하기

우리에게 익숙한..

중학교 1학년 때 배우는 에라토스테네스의 체

 

이 전에(과제할 때) 반복문을 돌려서 나머지가 0인지를 판별하는 식으로 소수를 판별했는데,

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

이번 백준 문제를 풀고 그 방식이 너무나도 느리다는걸 깨달았습니다.

 

그래서 나온 결론은 에라토스테네스의 체를 이용하는 방법입니다.

숫자 배열로 공간을 많이 먹기는 해도 속도는 훨 빠르더군요.

 

#include<stdio.h>

int main(void)
{
    int n, m;
    int i, j;
    int che[1000001] = {0,};
    che[1] = 1;

    scanf("%d %d",&m,&n);

    for(i=2; i<=n; i++)
    {
        for(j=2; i*j<=n; j++)
        {
            che[i*j] = 1;
        }
    }

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

    return 0;
}

위 문제를 해결한 코드입니다.

여기서 주목할 부분은 che(체)라는 배열을 필요한 숫자만큼 만들고 모두 0으로 초기화합니다.

0이면 소수, 1이면 합성수가 될 것입니다.

 

1부터 세므로 필요한 배열에 1을 더해서 만들어주고, 1은 소수가 아니므로 그냥 1을 집어넣어 줍니다.

 

여기서 서로 곱하는 수를 반복문을 돌려서 곱해줍니다. 그래서 나온 숫자 배열에 1을 넣어줍니다. 그러면 무언가를 곱해서 나온 숫자이므로 합성수가 될 것입니다.

for(i=2; i<=n; i++)

{

   for(j=2; i*j<=n; j++)

   {

      che[i*j] = 1;

   }

}

 

이후 che[숫자]가 0이면 소수, 1이면 합성수로 판단하도록 합니다.

 

이렇게 해서 시간을 절약할 수 있었습니다. 감사합니다.