유클리드 호제법또는 유클리드 알고리즘은 최대공약수를 구하는 알고리즘 중 하나이다. 호제법의 호는 서로 호(互)와 나눌 제(除)를 써서 서로 나눈다는 뜻을 가지고 있다.
2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r라고 하자. 이때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 이용해서 a, b를 계속해서 줄여나가다가 a%b(=r)이 될 때까지 나누면 그 수가 바로 최대공약수이다.
[ 예시 ]
1071과 1029을 입력받는다고 가정하자.
더 큰 수인 1071을 a로, 더 작은 수인 1029를 b로 둬야한다.(a>b)
1071 % 1029 = 42
1029 % 42 = 21
42 % 21 = 0 : 따라서 1071과 1029의 최대공약수는 21이다!
최대공약수(Greatest Common Divisor)는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. 예를 들어 12와 18의 최대공약수는 6이다. 최대공약수를 유클리드 호제법을 이용해서 구하는 코드는 다음과 같다. 단, a > b이여야 제대로 계산이 가능하다.
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a최소공배수(Least Common Multiple)는 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 예를 들어 12와 18의 최소공배수는 36이다. 최소공배수는 두 자연수의 곱 / 최대공약수로 구할 수 있다.
def lcm(a, b):
return int(a * b / gcd(a, b))