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?
2520은 1에서 10까지 숫자로 나머지 없이 나눌 수 있는 가장 작은 숫자이다.
1에서 20까지 숫자로 나눌 수 있는 가장 작은 양수는 무엇인가?
--------------------------------------------------------------------------
1에서 20까지 모두 곱해서 답을 구할 수 있을 것 같지만, 1에서 10까지 모두 곱하면 3,628,800으로 문제에서 제시한 2,520에 비해 1,440배 크다. 6이 있으면 앞에서 2, 3을 곱하지 않아도 되는 것이다.
여러 개 숫자에 대해 최소공배수를 구하는 것인데, 소인수분해를 하고 각 소수의 최대 제곱수를 구해서 곱하면 되지만, 이것을 프로그램으로 구현할 방법이 떠오르지 않아 반대로 접근하기로 했다. 중복된 곱셈을 하지 않기 위해서 2~20까지 숫자를 두고, 가장 작은 숫자부터 1씩 키워가면서 나눠지는 경우에는 나눈 숫자로 바꾼 형태로 해서 중복된 곱셈을 하지 않는 방식으로 구현하였다.
예를 들어 설명하면 2,3,4,5,6,7,8,9,10의 리스트를 두고 2로 중복곱셈을 하지 않기 위해 2로 나누면, 2,3,2,5,3,7,4,9,5가 되고 이것을 10까지 반복하고 곱하면 2,520이 되는 것처럼 20까지 반복해서 곱하는 방식으로 해결하였다.