최대공약수

⭐️ 반복문 이용

두 수 중 더 작은 값을 i에 저장한 후, i가 두 수의 공통된 약수인지 확인한다. 공통된 약수가 아니라면 i에서 1씩 빼가며 공통된 약수를 찾는다.

def min(a, b):  # 두 수의 min값을 구하는 함수
    if a > b:
        return b
    else:
        return a

def gcd(a, b):  # 두 수의 최대공약수를 구하는 함수
    i = min(a, b)
    while True:
        if a % i == 0 and b % i == 0:
            return i
        i = i - 1

⭐️ 유클리드 호제법

gcd(a, b) = gcd(b, a % b)이며 gcd(n, 0) = n이다.

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