Problem 5. 1 ~ 20 사이의 수로 나누어 떨어지는 가장 작은 수

Project Euler - 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까지의 모든 수로 나누어 떨어질 수 있는 가장 작은 수는 무엇일까요?

- 1 ~ 20까지의 최소공배수를 구하는 문제입니다.

유클리드 호제법

1. 큰 수에서 작은 수를 나눈 나머지를 구합니다.

 - 큰 수, 작은 수의 구분은 없고 처음 수와 나중 수가 의미가 있습니다.

2. 작은 수가 큰 수, 나머지가 작은 수의 역할을 하며 1의 과정을 다시합니다.

3. 2의 과정을 하다가 나머지가 0이면 종료합니다.

4. 마지막으로 나눈 값이 최대공약수 입니다. (아래 코드 중 int GCD(int num1, int num2) 함수 참고)

최소공배수

최소공배수 = 큰 수 * 작은 수 / 최대공약수

두 숫자 이상의 최소공배수 구하기

최소공배수 = 이전 숫자의 최소공배수 * 새로운 숫자 / 이전 숫자의 최소공배수와 새로운 숫자의 최대공약수

 - 모든 숫자가 끝날 때까지 반복

두 숫자 이상의 최대공약수 구하기

1. 처음 하나의 숫자를 최대공약수와 최소공배수로 정의합니다.

 - 숫자가 하나일 때에는 그 수가 최대공약수이자 최소공배수이기 때문입니다.

2. 지금까지 구해놓은 최대공약수와 새로운 수로 최대공약수를 구합니다.

3. 또 지금까지 구해놓은 최소공배수와 새로운 수로 최소공배수를 구합니다.

 - 최소공배수 * 새로운 수를 나눌때에는 현재 곱하는 두 수의 최대공약수로 나누어야 합니다.

4. 2, 3과정을 모든 숫자가 끝날 때까지 반복합니다.