유클리드의 호제법에 의한 최대 공약수를 구하는 방법

개요

유클리드의 호제법이란, 2개의 자연수의 최대 공약수(Gratest Common Divisor)를 구하는 수법의 하나입니다. 한 쪽을 다른 쪽으로 나누어 잉여를 구하고, 그 잉여를 사용하여 추가 나눗셈을 반복함으로써 최종적으로 잉여가 0이 된 시점에서 최대 공약수를 찾을 수 있습니다. 가장 오래된 알고리즘으로도 알려져 있으며, 기원전 300년경에 편찬된 유클리드의 「원론」에 그 기술이 있습니다.

구현 예

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider

주의점

엄밀하게는 피제수와 제수의 대소관계는 관계없다(피제수 쪽이 작은 경우, 피제수가 그대로 잉여가 되어, 다음의 처리로 제수와 바뀐다)입니다만, 본 기사에서는 직관적으로 알기 쉽게 하기 위해서 최초의 나눗셈으로 큰 쪽을 작은 쪽으로 나누도록 하고 있습니다.

참고

h tp : // Judge. 우아이즈. 아 c. jp / 온 네쥬 드게 /에서 sc 리 p 치온. jsp? D = A LDS1_1_B
https://ko.wikipedia.org/wiki/유클리드 호제법