[백준] 2609번 최대공약수와 최소공배수 (Python)

문제

www.acmicpc.net/problem/2609

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

 

코드

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

a,b = map(int,(input().split()))
g=gcd(a,b)
lcm = g * (a//g) * (b//g)

print(g)
print(lcm)

 

코드설명

유클리드 호제법은 최대공약수 구하는 공식이다.

a,b의 최대공약수는 b와 a%b의 최대공약수와 같다. 즉, GCD(a, b) = GCD(b, a%b)

gcd(24,16) => gcd(16,8) => gcd(8,0)

b가 0일때 gcd = a

 

최소공배수 공식은 LCM = GCD * a/gcd * b/gcd

=> 6 | 24 18

        ㅡㅡㅡㅡ

           4  3    => 6 * 4 * 3