유클리드 호제법?

유클리드 호제법은 위키피디아에 따르면

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 (opens new window) 또는 정식(整式)의 최대공약수 (opens new window)를 구하는 알고리즘 (opens new window)의 하나

로, 유클리드 호제법에 따르면, $a$>$b$일 때 $b$의 값을 $a$ mod $b$ 의 결과값으로 나눠주는 것을 반복하다 나눈 나머지가 0이 됐을 때의 $b$를가 바로 최대공약수이다.

구현방법

원리는 간단하다. $r$에 $a$ mod $b$를, $a$에 $b$를, $b$에 $r$을 대입한다. 이렇게 되면 다음 루프에서도 나머지값이 $b$ 자리에, 기존 $b$ 값이 $r$자리로 들어가 $b$의 값을 $a$ mod $b$의 결과값으로 나눌 수 있게 된다.

프로그래밍으로 구현 - 순서도와 테스트 케이스 표

프로그래밍으로 구현 - 실제 코드

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

print(gcdEuclid(12,18))