문제)
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까지 나눴을 때 나머지가 없는 수 중 가장 작은 수는 무엇인가?
Sol.)
2520은 어떤 수인가?
1에서 10부터 존재하는 소수들만의 곱인가?
확인해보자.
2*3*5*7 = 210 이므로 아니고...
2520을 소인수분해해보면
2520 = 210 * 12
= 2*3*5*7*3*4
= 2*2*2*3*3*5*7
일단 1부터 20까지 존재하는 소수를 나열해보면,
2, 3, 5, 7, 11, 13, 17, 19 이다.
모두 곱해보면, 9699690 이 나오네.
근데 이 수는 4,9,12,16,18,20 으로 나눠지지 않는다. 이들 수들의 공통점이 있는 것 같다.
2*2, 3*3, 2*2*3, 2*2*2*2, 2*3*3, 2*2*5
그러니까 2가 3개 더 있어야 되고, 3이 하나 더 있으면 해결될 것 같다.
9699690 * 8 * 3 = 232792560
프로젝트 오일러에서 확인해보면..
오, 정답이긴 한데.... 뭔가 찝찝하다.
좀 더 학문적으로 알고리즘으로 파헤쳐볼 필요가 있다.
232792560 = 2*2*2*2*3*3*5*7*11*13*17*19 인데,
1부터 20까지의 수로 나눠서 나머지가 없어야 하는 것이니
단순히 소수만을 곱하면 안 되는 것이었다.
20이하의 수 중,
2의 제곱수(2,4,8,16,32,....) 중 가장 큰 수는 16이고,
3의 제곱수(3,9,27,.....) 중 가장 큰 수는 9이고,
5의 제곱수(5,25,125,.....) 중 가장 큰 수는 25이며,
쭉쭉쭉.......
그렇다. 20이하의 소수 중에서 그 소수의 제곱수 중 20이하이면서 가장 큰 수들의 곱이 바로 우리가 원하는 수 찾는 것이다.
말이 길었는데
정리해보면 1에서 20까지의 수들의 최소공배수를 구하는 것이다. (16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 )
이걸 알고리즘이나 코드로 구현을 한다면,