[Python] 최대공약수, 최소공배수 구하기

# 최대공약수(유클리드 호제법 사용)
def ucle_max(a, b):
    if b>a:
        temp=a
        a = b
        b = temp
    while b> 0:
        c = b
        b = a % b
        a = c
    return a

# 최소공배수(두 수를 곱한 후 최대공약수를 나눌 경우 최소공배수가 됨)
def ucle_min(a, b):
    return a * b // ucle_max(a, b)

n1 = int(input('첫번째 수 입력 : '))
n2 = int(input('두번째 수 입력 : '))

print('최대공약수 : {0}'.format(ucle_max(n1, n2)))
print('최소공배수 : {0}'.format(ucle_min(n1, n2)))

 

유클리드 호제법

큰수에서 작은수의 나머지를 구함

(큰수 / 작은수)의 나머지

두 수의 작은수와 구해진 나머지를 나누 나머지를 구함

(작은수 / 구해진 나머지)의 나머지를 구함

반복하다가 나머지가 0일 경우 그 수가 최대공약수

 

최소공배수는 두 수를 곱한 후 구해진 최대공약수를 나눈다.