[백준 2609 파이썬] 최대공약수와 최소공배수 (실버5, 정수론)

알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : △(통과 후 풀이 참고를 통해 최적화)

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

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

num, div = b, a
rest = num % div
while rest != 0:
    num = div
    div = rest
    rest = num % div
print(div)
print(a*b // div)

풀이 요약

1. 최대공약수는 유클리드 호제법으로 구하면 된다.

   ex) 24와 18의 최대공약수 유클리드 호제법으로 구하는 과정

   • 24 % 18 = 6

   • 18 % 6 = 0 (나누는 수를 나눠지는 수로, 나머지를 나누는 수로 갱신)

   • 나머지가 0이 될 때, 그 때의 나누는 수가 최대공약수다(6)

2. 최소공배수는 두 수의 곱 나누기 최대공약수이다.

배운 점, 부족했던 점

• 최대공약수 = GCD(Greatest Common Divisor), 최소공배수 = LCM(Least Common Multiple)

• "최소공배수 = 두 수의 곱 / 최대공약수"를 알게 됐다.

  a = x * GCD(a, b)

  b = y * GCD(a, b)

  ab = x y * (GCD(a, b) ^ 2)

  LCM(a, b) = ab / GCD(a, b) = x y * GCD(a, b)