[C/C++] 프로젝트 오일러 #5 : 1~20으로 나누어지는 가장 작은 자연수(수학)

문제의 난이도가 조금씩 높아져 가는 것을 느끼네요.

 

이번 문제는 효율성을 충분하게 발휘할 수 있는 문제입니다.

 

 

가장 쉬운 알고리즘으로는,

1부터 차례대로 모든 수에 대해서 1부터 20까지의 숫자로 나누어 떨어지는 첫번째 수를 찾으면 쉽게 해결이 되겠지만, 그렇게 되면 너무 많은 수에 대해서 검사를 해야 합니다.

 

여기서는 유클리드 방법에 의해서 최대 공약수를 찾고, 그 수를 가지고 곱을 해내가는 방식으로 알고리즘을 생각했습니다.

 

유클리드 방법에 의해서 최대공약수를 찾는 것은, 두 수중 작은 수 N에 대하여 O(log N)의 알고리즘으로 찾을 수 있습니다.  그러면 결국 20까지의 숫자를 N으로 표현한다면 O(N log N) 알고리즘으로 답을 찾을 수 있습니다.

 

가장 쉬운 알고리즘이라고 소개한 경우에는 답을 대충 유추해도 100만 이상의 숫자가 나옵니다.  2, 3, 5, 7, 11, 13, 17, 19 라는 소수와 2라는 소인수는 4개, 3이라는 소인수는 2개가 나오니까요.  사실, 소수를 모두 알고 있다면, 

 

\[ \prod_p p^{\lfloor n/p \rfloor} \]

 

라는 계산식으로 찾을 수도 있습니다.  소수를 찾아내는 알고리즘 중 간단한 것을 이용해도 처음 말한 알고리즘보다 효율적으로 답을 찾을 수 있습니다.

 

 

int main()
{         
    int n = 20;         
    int c = 1;          
    for( int i = 2 ; i <= n ; i++ )         
    {                 
        if( c%i == 0 ) continue;                 
        int r = i;                 
        int s = c%i;                 
        while( r%s )                 
        {                         
            int t = r%s;
            r = s;
            s = t;
        }
        c *= i/s;
    }
    printf(" ans(%d)="%d\n" n, c);
}