[백준] 2609번 최대공약수와 최소공배수

1. 문제

 

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

 

2. 입력

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

 

3.출력

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

 

4. 풀이

import math

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

#최대공약수
print(math.gcd(a, b))
#최소공배수
print(math.lcm(a, b))

python은 math의 라이브러리가 있어서 수학의 대한 식이 나와 있다. gcd 는 최대 공약수 함수이고 lcm은 최소공배수 함수이다. 

 

5.다른 풀이

유클리드 호제법을 사용해서 푸는 사람들이 대부분 있어서 코드 리뷰를 하고 싶었다.

유클리드 호제법은 최대공약수를 쉽게 구할 수 있는 알고리즘 주의 하나이다. 이 알고리즘은 식을 간결하게 해주는 특징이 있다. 두 수 a 와 b가 있다고 할 때, a와 b의 최대공약수는 b와 a 와 b 나눈 나머지의 최대공약수가 서로 같다라는 것이다.

 

예시 입력으로 보면,

gcd(24, 18) = gcd(18, 6) = gcd(6, 0)인 것이다!

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

 

최소공배수 구하는 식은 a*b/gcd(a,b)이다 . 

 

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

def gcd(a,b):
  while b != 0: #b가 0이 될까지 돌린다.
      a = a % b
      a, b = b, a
  return a  # b가 0이 되면 while문이 끝나므로 a가 최대공약수 

# 최대공약수
print(gcd(a,b))

#최소공배수
print(a*b//gcd(a,b))