유클리드 호제법

1. 유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘

a와 b가 주어질 때, a를 b로 나눈 나머지가 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 과정을 반복하여 나머지가 0이 될 때까지 반복하면 a와 b의 최대공약수를 구할 수 있다.

2. 예제

① a = 54, b = 36

r1 = 54 % 36 = 18이므로

② a = 36, b = 18

r2 = 36 % 18 = 0이다.

③ a = 18, b = 0

∴ 최대공약수는 18이 된다.

 

def gcd(a, b):
  while b != 0:
    r = a % b
    a, b = b, r
  return a