[BOJ/Python] 2609. 최대공약수와 최소공배수

문제

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

입력

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

출력

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

 

<CODE & REVIEW>

최대공약수와 최소공배수는 3가지 방법으로 구할 수 있다. 

 

1) 최대공약수는 더 작은 값을 하나씩 줄여가며 for문을 돌립니다. a를 i로 나눴을 때, b를 i로 나눴을 때 둘다 나머지가 0인 값이 나오면 바로 출력해주고 for문을 끝냅니다. 이 때 출력되는 값이 가장 큰 공약수, 즉 최대공약수입니다.

최소공배수도 비슷한 방법으로 for문을 이용해서 코드를 짜면 됩니다. 달라지는 건 a,b 중 큰 값부터 하나씩 증가하면서 for문을 돌리는데, 이 때, a로 나눴을 때나 b로 나눴을 때나 나머지가 0인 j값을 출력하고 for문을 끝냅니다. 

이 방법은 시간 초과가 나옴.

a, b = map(int, input().split())
# 최대공약수
for i in range(min(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        print(i)
        break
# 최소공배수
for j in range(max(a, b), (a * b) + 1):
    if j % a == 0 and j % b == 0:
        print(j)
        break

 

 2) math 함수를 이용하는 방법입니다. 최대공약수는 gcd, 최소공배수는 lcm

import math

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

 

3) 마지막은 '유클리드 호제법'을 이용한 최대공약수와 최소공배수를 구하는 방법입니다.

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다.

기본 개념은 2개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

def GCD(a, b): # 최대공약수
    if b == 0:
        return a
    return GCD(b,a%b)
a, b = map(int, input().split())
print(GCD(a, b))
#최소공배수
print(int(a*b/GCD(a,b)))

 

 

 

<문제 출처>

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

2609번: 최대공약수와 최소공배수