[프로젝트 오일러] 5번 문제 & 풀이 (1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수)
Problem 5 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 처음 아이디어 이 문제는 최소공배수를 구하는 문제이다 숫자 4, 6의 경우, 이 때의 최대공약수(GCD)는 2, 최소공배수(LCM)는 12이고, 4 = GCD * 2, 6 = GCD * 3 에서 LCM = GCD * 2 * 3 = GCD * 2 X GCD * 3 / GCD 이다. 이 때, 추가로 숫자 7과의 최대공배수를 구하려면, 처음부터 다시 최대공약수&최소공배수를 구할 필요 없이, 앞서 구한 최소공배수인 12와 7 사의의 최소공배수를 구하면, 이 값이 4, 6, 7의 최소공배수가 된다. 같은 논리로, 1부터 차례대로 20..
2020. 5. 30.
