[Python] 백준 2609번 - 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

Solution

최대공약수 = 유클리드 호제법
최소공배수 = (A * B) / 최대공약수

유클리드 호제법이란
-> A % B = R
-> B % R = R2
-> R % R2 = R3
-> R2 % R3 = 0
위와 같은 식이 세워졌을 때 최대공약수는 R3이다.

내 코드

import sys

A, B = map(int, sys.stdin.readline().rstrip().split())
mul = A * B
while True:
    r = A % B
    if r == 0:
        print(B)
        break
    A = B
    B = r
print(mul//B)