프로젝트 오일러(Project Euler) 5번문제

Problem 5

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?

풀이

  사실 이문제는 계산기로 풀어서 부랴부랴 코드를 작성하였다. 그러다보니 좀 길어진듯 하다. 문제를 해결하는 법은 그닥 어렵지 않다. 1~10사이의 숫자들의 최소 공배수를 구하면되는데, 나는 소인수 분해를 이용해서 구해주었다. 아래 표는 1에서 10까지 가면서 최소공배수를 구해가는 과정이다.

	소인수	최소 공배수
1	1	1(제외)
2	2	2
3	3	2 x 3
4	2^2	2^2 x 3
5	5	2^2 x 3 x 5
6	2x3	2^2 x 3 x 5
7	7	2^2 x 3 x 5 x 7
8	2^3	2^3 x 3 x 5 x 7
9	3^2	2^3 x 3^2 x 5 x 7
10	2x5	2^3 x 3^2 x 5 x 7

코드를 짤때도 위와같은 순서로 작성하였다. 그냥 생각난대로 바로바로 짠거라 사실 좀 지저분한것도 없지않아 있으니 감안하고 봤으면 한다.

#include <stdio.h>
#include <math.h>    // pow를 사용하기 위한 라이브러리
 
void main()
{
    int primeFactor[21] = { 0, }, count = 0, num = 0;
    int answer = 1;
 
    for (int i = 2; i < 21; i++)
    {
        num = i;    // num가지고 소인수를 구함
        for (int j = 2; j <= i; j++)
        {
            while (1)    // while문에서 현재 숫자가 j로 몇번이나 나눠지는지 확인함
            {
                if (num % j == 0)
                {
                    count++;
                    num /= j;
                }
                else break;
            }
 
            if (primeFactor[j] < count)    // pirmeFactorp[j]보다 count가 크면 그 수로 바꿈
            {
                primeFactor[j] = count;
            }
            count = 0;
        }
    }
 
    for (int i = 2; i < 21; i++)    // 최소공배수
    {    // i^(배열안의 숫자) 계산과정
        answer *= pow(i, primeFactor[i]);
    }
    printf("%d\n", answer);
 
    return;
}

결과