에라토스테네스의 체

개론

정의
에라토스테네스의 체란 수학에서 소수를 찾는 방법 중 하나이다. 기존의 소수 찾는 방식으로 많이 사용하는 ‘나눠지지 않을 때 까지 나누기’는 결국에 완전탐색처럼 모든 경우의 수를 전부 검사해야하기 때문에 매우 많은 시간을 사용하게 된다. 물론 대부분의 경우 이 방법에서 문제가 생기지는 않지만 만약 큰 범위의 수가 대상이 된 경우, 정작 코어 로직이 아닌 소수구하기에서 타임 리밋이 나버릴 수 있게 된다. 그럴때 사용하기 매우 적절한 방법이 이 에라토스테네스의 체이다.

원리
원리는 간단하다. 매우 작은 소수에서 시작하여 그것의 배수들을 제외시켜간다면 결국 마지막에 남는 수들이 소수가 될 것이다. 코드 상에서도 간단한 반복문을 통해 이것을 구할 수 있는데, 동적 계획법에서 캐쉬배열을 사용하는 것 처럼 하나의 수 배열을 만들고 메모이제이션을 한다면 매우 간단하게 구할 수 있다. 이는 기존의 방법보다 훨씬 빠르게 소수들을 판별할 수 있게 해준다.

구현

void Eratos(int n)
{
    primeArray = new bool[n+1];

    for (int i = 2; i <= n; i++)
    {
        primeArray[i] = true;
    }

    for (int i = 2; (i*i) <= n; i++)
    {
        if (primeArray[i]) // 이전 수의 배수였을 가능성을 제외
        {
            for (int j = i*i; j <= n; j += i) // i*i를 통해 중복연산 제외
            {
                primeArray[j] = false;
                printf("%d ", j);
            }
        }
    }
}

위의 코드는 에라토스테니스의 체를 구현한 것으로 원하는 범위의 배열을 동적 할당하여 전역에 놓은 이후, 소수가 아닌 것들을 채워가는 방식으로 처리한다. 이 코드에서 주의 깊게 봐야 하는 것들이 몇 가지 있다. 먼저 중복연산의 제외방식이다. 일단, 반복을 피하기 위해 두번째 루프를 들어가기 전 이전에 검사했는지 if문으로 걸러내기 때문에 한번씩 더 연산하는 것을 피하게 해준다. 그리고 해당 차례의 제곱수를 시작점으로 잡아서 다시 한번 중복된 연산을 피하게 해준다.

적용

두 수 a,b를 입력으로 받고 그 수들 사이 범위안에 있는 모든 소수를 구하는 문제이다. 소스는 다음과 같다.

#include<cstdio>

bool *primeArray;

void Erato(int n)
{
    primeArray = new bool[n + 1];

    for (int i = 2; i <= n; i++)
    {
        primeArray[i] = true;
    }

    for (int i = 2; (i*i) <= n; i++)
    {
        if (primeArray[i])
        {
            for (int j = i*i; j <= n; j += i)
            {
                primeArray[j] = false;
            }
        }
    }
}

int main()
{
    int a, b;

    scanf("%d%d", &a, &b);

    Erato(b);

    for (int i = a; i <= b; i++)
    {
        if (primeArray[i])
            printf("%d\n", i);
    }
    return 0;
}