[알고리즘] 백준 2609 : 최대공약수와 최소공배수 - B1

2023.04.16 풀이

import sys
input=sys.stdin.readline
import math

a,b=map(int, input().split())

k=math.gcd(a,b)
print(k)
print(k*(a//k)*(b//k))

다른 풀이

a, b = map(int, input().split())

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

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

ref

check point

• 호제법
  a를 b로 나눈 나머지를 r이라 하면(a>=b) a와 b의 최대공약수 = b와 r의 최대공약수
  r이 0이 될 때 까지 반복.
  ref. 유클리드 호제법