[알고리즘] 최대공약수 구하기 - 파이썬

방식 1. 큰 수에서부터 나눠보며 깎아나가기(?)

def solution(a, b):
	i = min(a, b)
    while True:
    	if a % i == 0 and b % i == 0:
        	return i
        i = i - 1

 

방식 2. 유클리드

# 유클리드 알고리즘
# 수학자로 유명한 유클리드(Euclid)의 발견에 따르면, 최대공약수에 다음과 같은 성질이 있다.
# a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a%b)
# 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n

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