본문 바로가기

문제풀기/프로젝트 오일러

프로젝트 오일러 문제 - 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?

 

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 )

 

이걸 알고리즘이나 코드로 구현을 한다면,