최적화된 에라토스테네스의 체(Eratosthenes' sieve)

가장 기초 알고리즘을 이용한 에라토스테네스의 체(Eratosthenes' sieve)를 포스팅 한 적이 있고,

http://www.crocus.co.kr/576

비트 연산자를 이용하여 시간 복잡도 최적화와 공간 복잡도가 최적화 된 

에라토스테네스의 체(Eratosthenes' sieve)를 포스팅 한 적이 있다.

http://www.crocus.co.kr/593

사실 위의 비트 연산자를 이용하는 에라토스테네스의 체가 가장 최적화 된 코드이지만,

실전에서는 저만큼까지 생각하기가 힘들고, 코드가 다소 길기에

이번에는 시간 복잡도가 최적화 된 코드에 대해 알아보고자 한다.

정말 hard한 문제가 아니면 이 방식으로 웬만한 문제는 모두 해결이 가능하다.

에라토스테니스 체를 설명 하기위해 바로 코드를 확인해보자.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <memory.h>
 
#define MAX_N 100
 
using namespace std;
 
int n = MAX_N;
bool isPrime[MAX_N + 1];
 
void eratosthenes()
{
    memset(isPrime, 1, sizeof(isPrime));
 
    isPrime[0] = isPrime[1] = false;
 
    int sqrtn = int(sqrt(n));
 
    for (int i = 2; i <= sqrtn; i++)
        if (isPrime[i])
            for (int j = i*i; j <= n; j += i)
                isPrime[j] = false;
}
 
int main()
{
    eratosthenes();
 
    for (int i = 0; i <= MAX_N; i++)
        if (isPrime[i])
            cout << "소수 :: " << i << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

우선 가장 기본적인 에라토스테네스의 체가 어떻게 동작하는지 안다는 가정하에 설명하려 한다.

여기서 최적화 되기전과 후의 가장 다른점 중 하나는 의 방식을 이용하고 있다는 것이다.

으로 문제를 접근해도 되는 이유는 다음과 같다.

합성수 n이 만약 p*q로 표현이 된다면 한 수는 항상 이하, 다른 한 수는 항상 이상이기에

i < n까지 순회하지 않고, i <= 까지 순회해도 괜찮다.

이는 이미 수학자들에 의해 증명이 되어있고 그 증명을 잠깐 살펴보자.

증명 

Let's say m = sqrt(n) then m × m = n. Now if n is not a prime then n can be written as n = a × b, so m × m = a × b. Notice that m is a real number whereas n, a and b are natural numbers.

- 루트 n = m이라 생각한다면, m*m = n이 자명하다. 만약 n이 소수가 아니면 n = a*b로 쓸 수 있고, m*m = a*b가 될 것이다.

이때 알고있어야 하는 것은 m은 실수(루트 n을 통해 나온 m이니)인 반면, n, a, b는 자연수이다.

Now there can be 3 cases:

- 이제 3가지 경우를 나타낼 수 있다.

a > m ⇒ b < m

a = m ⇒ b = m

a < m ⇒ b > m

In all 3 cases, min(a, b) ≤ m. Hence if we search till m, we are bound to find at least one factor of n, which is enough to show that n is not prime.

- 이 3가지 경우를 이용하면, min(a,b) <= m이다. 따라서 만약 우리가 m까지 조사를 한다면, 우리는 적어도 하나가 n의 인수임을 경계지을 수 있다. 결국 이것을 통해 n이 소수가 아닌지 보여줄 수 있다.

(생각해보면 이해가 될 것이다.)

결국 이를 통해 isPrime[i] == 1이면 i는 소수임을 알 수 있는 알고리즘이 완성된다.