수학 알고리즘 - 유클리드_(아직 완벽히 이해 X)

유클리드 알고리즘

최소 공약수를 구하는 효율적인 알고리즘이다.

두 수의 최소 공약수를 구하기 위해서, 한 수를 다른 한 수로 나눈 나머지가 0이 될 때, 두 수의 최소공약수는 나눈 수(즉 다른 한수) 가 된다.

나머지가 0이 안나왔을 경우, 한 수는 다른 한수로, 다른 한 수는 나머지를 대입해서 연산을 반복한다.

왜 큰 수 % 작은 수 가 아니여도 되는거지? 하

예제코드

def euclidean(m,n):
    if m == 0 or n == 0:
        return max(m,n)
    small_num = min(n,m)
    big_num = max(n,m)

    mod = big_num % small_num
    while mod != 0:
        big_num,small_num = small_num,big_num
        mod = big_num % small_num
    return small_num

print(euclidean(4,2))       #2
print(euclidean(4,4))       #4
print(euclidean(4,0))       #4