[백준/파이썬] 2609번: 최대공약수와 최소공배수

문제

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

해설

최대공약수란?

두 수가 공통으로 가지고 있는 약수 중 가장 큰 수이다.

최소공배수란?

두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수이다.

---

파이썬은 크게 2가지 방법을 이용해 최대공약수와 최소공배수를 구현할 수 있다.
유클리드 호제법을 이용한 방법과 math 라이브러리를 사용하는 방법이 있다.

유클리드 호제법이란?

둘 이상의 자연수의 최대공약수를 구하는 알고리즘이다.
2개의 자연수 큰 수(a), 작은 수(b), a를 b로 나눈 나머지(r)가 있을 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

코드

# 유클리드 호제법
import sys
input = sys.stdin.readline

def gcd(a,b):
	while b > 0:
    	a,b = b,a%b
    return a
    
def lcm(a,b):
	return a * b // gcd(a,b)
    
a,b = map(int,input().split())
print(gcd(a,b))
print(lcm(a,b))

코드2

# math library
import sys, math
input = sys.stdin.readline

a,b = map(int,input().split())
print(math.gcd(a,b))
print(math.lcm(a,b))