[BOJ_2609]최대공약수와최소공배수

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1 복사

24 18

예제 출력 1 복사

6
72

풀면서 느낀점

최대공약수와 최대공배수는 푸는 방법이 여러가지이다.

math 라이브러리 사용방법

import math

A, B = map(int, input().split())

gcd = math.gcd(A, B)
lcm = math.lcm(A, B)
print(gcd)
print(lcm)

최대 공약수: math.gcd는 3.5 이상 지원

최대 공배수: math.lcm는 3.9 이상 지원해준다.

백준이나 swea 에서는 최근에 나온 파이썬 3.9까지는 지원하지 않는다.

그러므로 정석대로 푸는 방법을 알아보자

유클리드 호제법

유클리드 호제법은 GCD를 쉽게 구할 수 있는 알고리즘 중 하나이다.

유클리드 호제법 알아보기

a와 b (a > b)가 있을때, a 와 b의 최대공약수 G는 b와 a%b(a를 b로 나눈 나머지)의 최대공약수 G와 같다.

이말은 gcd(24,18) = gcd(18,6) = gcd(6,0)인 것이다.

여기서 b가 0이 되는 순간의 6이 바로 최대 공약수가 된다.

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
  if m % n == 0:
		return n
	else:
		return gcd(n, m%n)

최대공약수를 구했다면 최소공배수는 바로 구할 수 있다.

A = x * gcd B = y * gcd 이므로

최소공배수는 x * y * gcd

따라서 lcm = A * B // gcd

이 수가 최소공배수인 이유는 이 수를 A로 나눠도 나누어 떨어지고 B로 나눠도 나누어떨어지는 수 중에서 가장 작은 수이기 때문이다.

나의 풀이

파이썬 3.5 정도는 swea도 탑재하고 있기때문에 gcd를 math 라이브러리를 사용해서 구했다.

lcm은 라이브러리 사용이 안되니 위의 방법으로 구하는 하이브리드(?) 전략으로 코드 길이를 줄였다.

import math

A, B = map(int, input().split())

gcd = math.gcd(A, B)
lcm = A * B // gcd

print(gcd)
print(lcm)