[Python] 최대공약수 구하기

첫 번째 방법

def gcd(a, b):
    i = min(a, b) #1
    while True:
        if a % i == 0 and b % i == 0: # 2
            return i #3
        i -= 1 #4

print(gcd(60, 24))

1. 두 수 중에 더 작은 수를 i에 저장한다.

2. i가 두 수의 공통된 약수인지 확인한다.

3. 만약 공통된 약수라면 결과값을 돌려주고 종료한다.

4. 아니라면 i를 1 감소시키고 2번으로 돌아가 반복한다.

 

두 번째 방법

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

print(gcd(60, 24))

이 방법은 유클리드 알고리즘을 이용한 방법이다.

 

a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다.

즉, gcd(a, b) = gcd(b, a%b)

어떤 수와 0의 최대공약수는 자기 자신이다. 

즉, gcd(n, 0) = n이다.