BOJ-Algorithm
백준 2609 - 최대공약수와 최소공배수
bellhundred
2022. 1. 9. 01:52
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
a,b = map(int, input().split())
def GCD(x,y):
while(y):
x,y = y,x%y
return x
def LCM(x,y):
result = (x*y)//GCD(x,y)
return result
print(GCD(a,b))
print(LCM(a,b))
유클리드 호제법을 활용하는 문제다. 호제법 공식만 알면 금방 풀 수 있다.