유클리드 알고리즘

유클리드 알고리즘

유클리드 알고리즘이란?

• 두 수의 최대공약수를 알아내는 알고리즘이다.

알고리즘 공식

• 1. 큰수에서 작은수를 빼고 둘중에 하나라도 0이되면 그 중에서 큰 수를 리턴하면 된다

def gcd(a, b):
    while a != 0 and b != 0:
        if(a>b):
            a = a - b
        else:
            b = b - a
    return a + b

또 다른 방법은 재귀함수를 호출해서 하는 방법.

def gcd2(a,b):
    if(b == 0):
        return a
    else:
        return gcd2(a, a%b)