최대공약수/최소공배수 - 백준 2609 [Python]

최대공약수 (GCD )를 구하는 빠른 방법은 유클리드 호제법을 이용하면 된다.

• a를 b로 나눈 나머지를 r이라고 했을 때
• GCD(a,b) = GCD(b,r)과 같다.
• r이 0이면 그때 b가 최대 공약수이다.
• GCD(24,16) = GCD(16,8) = GCD(8,0) = 8

최소공배수 (LCM) 도 최대공약수를 구한 것과 비슷하게 적용하여 구하면 된다.

•  LCM(A,B) = GCD(A,B) * (A/GCD(A,B)) * (B/GCD(A,B))

Example)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

Answer)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
a,b = map(int, input().split())
g = gcd(a, b)
print(g)
print(a*b//g)