[알고리즘] 유클리드 호제법(GCD, LCM)

유클리드 호제법을 사용하면 최대공약수와 최소공배수 문제를 해결하는데 유용하게 사용할 수 있습니다.

최대공약수

두 수 a, b 가 있을 때 큰 수를 작은수로 나누었을 때의 나머지를 이용하여 나머지가 0일 될때까지 반복해서 비교합니다.

최소공배수

최소공배수는 두 수의 곱을 최대공약수로 나누면 구할 수 있습니다.

40 vs 3

1. 40과 3 비교 => 40 % 3 = 1
2. 1과 3 비교 => 3 % 1 = 0
   → 40과 3의 최대공약수는 1입니다.
3. 40 * 3 / 1 = 120
   → 40과 3의 최소공배수는 120입니다.

25 vs 50

1. 25와 50 비교 => 50 % 25 = 0
   → 25와 50의 최대공약수는 25입니다.
2. 25 % 50 / 25 = 50
   → 25와 50의 최소공배수는 50입니다.

10 vs 4

1. 10과 4 비교 => 10 % 4 = 2
2. 2와 4 비교 => 4 % 2 = 0
   → 10과 4의 최대공약수는 2입니다.
3. 10 * 4 / 2 = 20
   → 10와 4의 최소공배수는 20입니다.