유클리드 호제법이란?
유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘 중 하나이다.
방법
2개의 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이 성질을 반복적으로 이용하여 r이 0이 되었을 때 나누는 수(b) 가 a와 b의 최대 공약수이다.
예시
24와 9의 최대 공약수를 구해보자.
a = 24, b = 9 이라고 할 때, r은 a%b(a를 b로 나눈 나머지) 이므로 r = 6이 된다.
그러면 24와 9의 최대 공약수는 9와 6의 최대 공약수 와 같다는 것을 알 수 있다.
다시 9와 6의 최대 공약수를 구하기 위해 a = 9, b = 6이라 하면 r = 3이 되므로 9와 6의 최대 공약수는 6과 3의 최대 공약수 와 같다는 것을 알 수 있다.
다시 6과 3의 최대 공약수를 구하기 위해 a = 6, b = 3이라 하면 r = 0이 되고, 이 때 나누는 수가 b 이므로 24와 9의 최대 공약수는 3 이라는 것을 알 수 있다.
코드 구현
아래는 유클리드 호제법을 이용하여 최대 공약수를 구하는 함수를 구현한 자바, 파이썬 소스 코드이다. 여기서는 while 반복문을 이용하여 구현했지만 재귀 호출을 이용하여 구현할 수도 있다.
JAVA
public class GCD {
// a와 b는 양의 정수
public static int gcd(int a, int b) {
int tmpA;
while (b != 0) {
tmpA = a;
a = b;
b = tmpA % b;
}
return a;
}
public static void main(String[] args) {
int a = 24;
int b = 9;
int result = gcd(a, b);
System.out.print(a + "와 " + b + "의 최대 공약수는 ");
System.out.println(result + "입니다.");
// output: 24와 9의 최대 공약수는 3입니다.
}
}PYTHON
# a와 b는 양의 정수
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
if __name__ == "__main__":
a, b = 24, 9
result = gcd(a, b)
print(f"{a}와 {b}의 최대 공약수는 {result}입니다.")
# output: 24와 9의 최대 공약수는 3입니다.참고 자료
- 유클리드 호제법 - 수악중독 (유클리드 호제법 증명)
- 최소공배수 백준 문제 (유클리드 호제법을 이용한 문제)
