[백준] 13241번: 최소공배수 파이썬

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

 

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

효율적으로 최소공약수를 구하는 방법은 유클리드 호제법을 사용하는 것이고, 이를 이용해 최소공배수도 간단히 계산할 수 있습니다.

유클리드 호제법

 

- 두 수 `x`와 `y`가 있을 때, `x`를 `y`로 나눈 나머지를 계속 구하면서 `y`가 0이 될 때까지 반복헌다.
- 최종적으로 남은 `x`가 최대공약수가 된다.

최소 공배수 구하는 방법

- 두 수의 곱을 최대 공약수로 나누면 최소 공배수가 나온다.

풀이

import sys

def gcd(x, y):
  while y > 0:
    x, y = y, x%y
  return x

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

a, b = map(int, sys.stdin.readline().split())
print(lcm(a,b))

코드 설명
1. `gcd` 함수: 유클리드 호제법으로 최대 공약수를 계산.
2. `lcm` 함수: 두 수의 곱을 최대 공약수로 나누어 최소 공배수을 계산.
3. 마지막으로 입력받은 두 수 `a, b`의 최소 공배수를 출력.