[백준/1934] 최소공배수 feat. 유클리드 호제법

📝 정수론_ 최소공배수

정수론은 정수를 다루는 학문으로, 약수와 배수/몫과 나머지에 대해 탐구한다.

컴퓨터 발달 이후 정수론의 유용성은 급상승했다.

현대 암호의 원리가 두 개의 큰 소수를 곱하는 것은 쉽지만, 이 결과를 다시 소인수분해하는 것이 어렵다는 것이 기반이기 때문이다.

뿐만 아니라 컴퓨터를 이용한 계산이나 메모리 설계 등에서도 정수론은 다양하게 쓰인다!

 

최소공배수(LCM, Least Common Multiple)는 최대공약수(GCD, Greateast Common Division)와 함께 정수론의 첫 번째 내용이다. 앞의 유클리드 호제법에서 유클리드 알고리즘을 통해 GCD와 LCM을 다루었으니, 이 포스팅에서는 내장함수를 기록하겠다.

---

💻 전체 코드

import sys
import math
n = int(sys.stdin.readline())

for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    print(math.lcm(a,b)) # 최소공배수 
    # 최대공약수는 math.gcd(a,b)이다.