[PYTHON] 최대 공약수, 최소 공배수 - gcd(), lcm()

gcd() - 최대 공약수 (GCD, Greatest Common Divisor)

: 둘 이상의 정수의 공약수 중에서 가장 큰 값 반환

 

lcm() - 최소 공배수 (LCM, Least Common Multiple)

: 둘 이상의 정수의 공배수 중에서 가장 작은 값 반환

import math

#최대공약수
print(math.gcd(2,4))
print(math.gcd(3,6,9))

#최소공배수
print(math.lcm(2,4)) 
print(math.lcm(3,6,9))

2
3
4
18

 

# 직접 구현하는 방법

#최대 공약수 - 재귀로 구현
def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

#최개 공약수 - while 문으로 구현
def gcd2(n, m):
    while m > 0:
        n, m = m, n % m
    return n

#최소 공배수
def lcm(n, m):  
    return n // gcd(n, m) * m

print(gcd(2,4))
print(gcd2(2,4))
print(lcm(2,4))

2
2
4