에라토스테네스의 체를 통해 소수 문제 정복 :: 마이구미

이번 글의 주제는 '에라토스테네스의 체' 라는 알고리즘이다.

소수를 구할 때 많이 활용되고 있다.

일단 가장 순수하게 소수를 구하는 방법을 접근해보자.

boolean isOK;
for(int i=start;i<=end;i++) {
    isOK = true;
    for(int j=2;j<=i;j++) { // i 까지 루프
        if(i % j == 0) {
            isOK = false;
            break;
        }
    }
    if(isOK && i != 1) System.out.println(i);
}

소수인지 판별하고자 하는 수를 2부터 자신의 수까지 루프를 돌면서 나머지 연산을 통해 구현되었다.

이 순수한 방법의 문제점이 무엇일까?

그렇다. 데이터가 커지면 커질수록 루프 횟수도 그만큼 증가한다는 것이다.

break를 건다고 해도 우리는 최악의 경우를 생각해야만한다.

시간복잡도로 나타내도 n제곱이다.

그래서 나온 방법이 제곱근이다.

자신의 수(i)까지 도는 것이 아니라 이 수(i)에 제곱근을 씌우는 것이다.

아래를 보자.

boolean isOK;
for(int i=start;i<=end;i++) {
    isOK = true;
    for(int j=2;j<=(int)Math.sqrt(i);j++) { // i의 제곱근까지 루프
        if(i % j == 0) {
            isOK = false;
            break;
        }
    }
    if(isOK && i != 1) System.out.println(i);
}

그렇다면 이러한 제곱근 방식의 성립이 어떻게 되는지 알아보자.

어떤 수 n은 두 수(a, b) 의 곱으로 나타낼 수 있다. 

예를 들어 12는 2*6 , 3*4 나타낼 수 있다.

두 수의 작은 값들을 보면 2, 3이다.

이 작은 값들을 다시 n을 나누어보면, 짝이였던 6, 4를 구할 수 있다.

그리하여 작은 수들만으로 소수 판별이 가능하다는 것이다.

수식으로는 아래와 같다.

a >= √n 이면, a * b = n = √n * √n 이므로, b<=√n 된다.

이 방법도 나쁘지는 않지만 더 효율적인 알고리즘이 이번 글의 주제이다.

이제 에라토스테네스의 체 알고리즘을 구현해보자.

먼저 위키의 정의를 보자.

그림의 경우, $${\displaystyle 11^{2}>120}이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

정의에서 보듯 "2, 3, 5, 7 배수를 지운다" 라고 볼 수 있다.

특정 수의 배수만 지우는 이유는 무엇일까?

자세히 살펴보면 특정 수의 배수만 지우는 것이 아니다.

8은 누구의 배수인가? 9는 누구의 배수인가? 10은 누구의 배수인가?

그렇다. 7 이후의 수들은 이미 이전의 수의 배수이다.

구현 또한 간단하다. 아래를 보자.

int rootSqrt = (int) Math.sqrt(n);
for(int i=2;i<=rootSqrt;i++) {
    if (array[i]) {
        // 이미 걸려진 수의 배수는 skip
        continue;
    }
    for(int j=i+i;j<=1000000;j+=i) {
        array[j] = true;
    }
}

이 알고리즘의 정의와 접근 방식만 이해한다면, 구현 상의 어려움의 전혀 없다.

두 번째 반복문에서 i의 배수들을 걸러낸다.

위 코드는 쉽게 이해하리라 생각한다.

이해한 후 소수 문제들을 풀어보길 권장한다.

백준 알고리즘 1929번, 1978번, 2581번, 1747번, 1990번

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

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

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

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

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

에라토스테네의 체 알고리즘이 소수 구할 때 가장 좋은 알고리즘이라고는 말할 수 없다.

하지만 대중화되었고, 효율적이기에 많이 사용하고 있는 알고리즘이다.

더 효율적이고 좋은 알고리즘은 존재한다.

N까지 소수 검사할 때 N의 제곱근까지 하는 이유

http://sprexatura.blogspot.kr/2016/05/n-n-square-root-of-n.html