최대공약수(유클리드 알고리즘)와 최소공배수 찾기

- 유클리드 알고리즘: 최대 공약수 찾기 알고리즘
  - 최대 공약수(GCD, Greatest Common Divisor): 

1번: 재귀 함수 이용

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

print(gcd(6, 24)) # 6

2번: 재귀 함수 X

def gcd2(a, b):
    gcd = 1
    for k in range(2, min(a, b) + 1):
        while a % k == 0 and b % k == 0:
            a //= k
            b //= k
            gcd *= k

    return gcd


def lcm(a, b):
    return a*b//gcd2(a, b)

print(gcd2(14, 42)) # 14
print(lcm(14, 42)) # 42

- 출처: m.blog.naver.com/okkam76/221306562506

- 최소공배수(LCM, Least Common Multiple) 찾기
  - 최소 공약수 함수 활용 가능
  - gcd는 위의 둘 중 하나 선택하면 됨

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

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

print(gcd(6,14)) # 2
print(lcm(6,14)) # 42