최대공약수, 최소공배수

# 최대공약수

1. while 문 (작은 수를 1씩 빼가면서 큰 수에 나눔)

gcd = a if a < b else b
def gcd:
    while True:
        if a%gcd==0 and b%gcd==0:
            break
        gcd -= 1
    return gcd

2. 유클리드 호제법 (나머지 이용)

gcd = a if a < b else b
def gcd(a, b):     
    while(b):
        a, b = b, a%b
    gcd = a
    return gcd

3. 재귀 함수

def gcd(a,b):    # 재귀 함수
    return b if (a==0) else gcd(b%a,a)   

def gcd(a, b):    # 재귀 함수
    if b == 0:
        return a
    return gcd(b, a%b)

4. math 모듈 이용

# math 모듈 이용
from math import gcd
gcd = gcd(a, b)

 

 

# 최소공배수

- 앞선 gcd 함수들 이용

def gcd(a, b):    

def lcm(a, b):    
    lcm = (a*b)//gcd(a, b)
    return lcm