[백준]2609-최대공약수와 최소공배수 구하기

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

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

x,y=map(int,input().split())

def gcd(x,y):
    mod =1
    if(y>x):
        x,y=y,x
    while(mod!=0):
        mod = x%y
        x=y
        y=mod
    return x

def lcm(x,y):
    a=x*y/gcd(x,y)
    return int(a)

    
print(gcd(x,y))
print(lcm(x,y))

---

# 유클리드 호제법

---

유클리드 호제법은 최대공약수를 구하기 위한 방법이다.

우리가 일반적으로 구할 때는 주로 소인수분해를 통해서 하지만

수가 커질 수록 너무 비효율적이기 때문에 이를 통해서 최대공약수를 구한다.

---

# 최소공배수 구하기

---

두 수의 곱 = 최대공약수 * 최소공배수 이므로 두 수의 곱은 최대공약수로 나눠서 구할 수 있다.