[BOJ] 2609 최대공약수와 최소공배수 (Python / 파이썬)

🧷 문제

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

두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 문제이다.

🛠 풀이

이 문제는 유클리드 호제법을 이용해 최대 공약수와 최소 공배수를 구하면 된다.

Step 1.
 유클리드 호제법을 이용해 최대공약수를 구한다.

• 유클리드 호제법
  : 2개의 자연수의 최대공약수를 구하는 알고리즘이다.
  "a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다."

  두 수 x와 y가 있을 때, (단, x >= y)
  def gcd(x, y):
    while b > 0:
        a, b = b, a % b
    return a

🖊 나의 코드

import sys

input = sys.stdin.readline

def GCD(a, b):
    while b > 0:
        a, b = b, a % b
    return a

if __name__ == "__main__":
    a, b = map(int, input().split())
    x, y = (b, a) if a > b else (a, b)

    gcd = GCD(x, y)

    lcm = a * b // gcd

    print(gcd)
    print(lcm)