1. 유클리드 호제법/알고리즘 (Euclidean Algorithm)
ㅇ 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘
ㅇ 최대공약수를 구하는 통상적인 방법으로는,
- 두 수를 소인수분해한 후, 그 중 공통되는 소수 중 제일 큰 것을 찾아가는 복잡한 방법을 씀
- 그러나, 소인수분해(어떤 수를 소수의 곱셈 형태로 인수분해하는 것) 자체도 쉽지 않음
- 또한, 두 약수 리스트 중 공통으로 들어있는 제일 큰 수를 찾는 것도 만만치 않음
2. 유클리드 호제법/알고리즘의 표현
ㅇ 두 수의 나눗셈을 반복하여 나머지가 0이 될 때 최대공약수가 구해지는 방법
ㅇ 例) gcd(21,9) → a = 21, b = 9
- a = b x q + r ☞ 나눗셈 관계식 참조
- 21 = 9 x 2 + 3 → b = 9, r = 3
. 여기서, 나온 나머지 3으로, 방금 나누어지는데 사용된 수 9를 나눔
- 9 = 3 x 3 + 0 → b = 3, r = 0 (나누어떨어짐)
. 여기서, 나머지가 0이 되므로, 이때 나누는 수 3이 최대공약수가 됨
- 따라서, gcd(21,9) = 3
ㅇ 알고리즘 표현 형태
ㅇ 입력 : r[0], r[1]
ㅇ 출력 : gcd ( r[0], r[1] )
Euclidean ( r[0], r[1] ) {
초기화 : i = 1 ;
while ( r[i] ≠ 0 ) {
r[i] = r[i-2] mod r[i-1] ;
}
return gcd ( r[0], r[1] ) = r[i-1]
}
※ 결국, 유클리드 알고리즘은,
- 단순히 나눗셈 만 되풀이하는 것 만으로도 최대공약수가 구해지게 됨
. 즉, 나눗셈을 되풀이하다가 마지막에 나누어떨어질 때,
. 그 때 나누는 수가 최대공약수가 됨
※ 한편, 마지막이 1이 되는 경우(즉, 두 수의 최대공약수가 1 인 경우)에,
- 이 때의 두 수는 서로소(Relatively Prime) 라고 함