GCD

[2609 - 최대공약수와 최소공배수] 유클리드 호제법

유클리드 호제법 최대공약수 ( GCD : Greatest Common Divisor ) 두 수 a, b (a > b)인 경우 a % b = 나머지(r)이라고 할 때 gcd(a, b) = gcd(b, r) 이므로 나머지가 0일때 까지 반복할 때 b의 값이 최대공약수 (GCD)가 된다 최소공배수 ( LCM : Least Common Multiple ) 두 수의 곱 / 최대공약수 = 최소공배수 즉 a * b / gcd 값이 최소공배수 (LCM)가 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Output..