최대공약수(Greatest common divisor)란?
"0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다."
최대공약수를 구하는 가장 대표적인 방법
(소인수분해와 나눗셈을 이용하는 방법)은
소인수분해 원리에 기반을 두기에, 정수의 크기가 커질수록
직접 소인수분해 하기엔 부담이 된다.
이때 효과적인 방법은 나눗셈 정리에 기반을 둔
유클리드 호제법을 사용하는 것이다.
유클리드 호제법이란(Euclidean algorithm)?
"2개의 자연수 또는 정식의 최대공약수를 구하는 인류 최초의 알고리즘이다."
두 양의 정수 a , b (a < b)에 대하여 a = b * q + r (0≤ r < b)이라 하면,
a , b 의 최대공약수는 b , r 의 최대공약수와 같다.
즉 gcd(a , b) = gcd(b , r)
r = 0이라면 a , b의 최대공약수는 b가 된다.
예시로 1234567과 12345의 최대공약수를 위 알고리즘을 통하여 계산하면,
1234567 = 12345 * 100 + 67
12345 = 67 * 184 + 17
67 = 17 * 3 + 16
17 = 16 * 1 + 1
16 = 1 * 16
따라서 gcd(1234567 , 1234) = 1이다.
해당 알고리즘은 자바 코드로 이렇게 나타낼 수 있다.
출처 : https://www.w3resource.com/java-exercises/basic/java-basic-exercise-157.php