[백준 / 파이썬] 2609번 최대공약수와 최소공배수

a,b = map(int, input().split())

def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
print(gcd(a, b))

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

 

유클리드 호제법

- a를 b로 나눈 나머지 r

- a와 b의 최대공약수는 b와 r의 최대공약수

- a와 b의 최대공약수는 b와 a%b의 최대공약수

gcd(24, 18) = gcd(18, 6) = gcd(6, 0)

b가 0이 되는 순간이 최대공약수 6

 

최대공약수를 K라고 한다면

a = K * x

b = K * y

이때 K가 최대공약수이기 때문에 x, y는 서로소

a * b = K * K * x * y

최소공배수는 a * b / K

 

import math

a, b= map(int, input().split())

print(math.gcd(a, b))
print(math.lcm(a, b))

math 모듈 사용하면 이렇게 간단하게도 가능!