#2609 최대공약수와 최소공배수🐄

문제📝

결과😍

코드💻

n, m = map(int,input().split())

def gcd(n, m):
  while m>0:
    n, m = m, n % m
  return n

def lcm(n, m):
  return n*m//gcd(n, m)

print(gcd(n, m))
print(lcm(n, m))

풀이💡

유클리드 호제법을 사용하여 푸는 문제이다.

• n, m의 최대공약수 : m, n을 m으로 나눈 나머지의 최대공약수
• n, m의 최소공배수 : n과 b의 곱을 n과 m의 최대공약수로 나눈 값

• 유클리드 호제법
  : 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘
  2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b),
  a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

---

참고🙏

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