Project Euler - 문제 5번

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

 문제 5번 : 2520은 1부터 10까지 나머지 없이 나누어지는 가장 작은 숫자이다. 그러면 1부터 20까지 나머지 없이 나누어지는 가장 작은 숫자는 얼마인가?

---

 문제는 생각보다 간단합니다. 그런데, 단순하게 1부터 20까지 곱하면 그 숫자는 가장 작은 숫자가 아닙니다. 왜냐하면, 4로 나누어지는 수는 이미 2로 나누어지기 때문이지요. 그래서 중복되게 나누어지는 부분을 최소화해서 가장 작은 숫자를 찾는 것이 목적입니다.

 제가 문제를 푼 방법은, 20 이하의 모든 소수를 찾고, 그 소수의 n제곱이 20 이하인 경우에 그 숫자를 곱해가면서 원하는 숫자를 찾았습니다. 말이 약간 복잡한데, 예를 들어서 2라는 소수가 있으면 \(2^4=16\)은 20보다 작기 때문에 20보다 작은 숫자 중에서 2의 배수로 가장 큰 16을 곱하고 그 이후에 2로 나누어 떨어지는 숫자들은 모두 곱하지 않는 것이지요. 이런식으로 각각의 소수들의 가장 큰 가능성들을 곱합으로써 중복되는 곱들을 모두 피할 수 있게 됩니다.

for(int i = 2; i < 20; i++)
{
 for(j = 2; j < i; j++)
 {
  if(i%j == 0)
   break;
 }
 if(i == j)
 {
  for(int k = j; k < 20; k = k*j)
   result = result * j;
 }
}

 그래서 위와 같은 코드를 통해서 중복되지 않게 가장 최소의 숫자를 만들어 나갈 수 있고 그 결과는 아래와 같습니다.

 생각보다 큰 수가 나오긴 했지만, 시간은 1ms 이하로 걸리면서 손쉽게 답을 얻었습니다.