백준 #2609 최대공약수와 최소공배수(파이썬) : 유클리드 호제법

오늘의 한 마디
최대공약수, 최소공배수 구하기도 어렵네;;

• Baekjoon 문제 링크
• solved.ac > 문제 > CLASS 2에 수록된 문제입니다.

문제

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

입력

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

출력

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

예제 입력 1

24 18

예제 출력 1

6
72

발상

최대공약수 : GCD(Greatest Common Divisor)
최소공배수 : LCM(Least Common Multiple)

유클리드 호제법

내가 다시 풀어서 설명하는 것보단,
정말 잘 설명되었다고 생각했던 이 링크를 한번 읽는게 더 도움될 듯하다.

위 링크에서 사용했던 예시만 한번 다시 설명해보겠다.

Q. 1112와 695의 최대공약수는 무엇인가?

A1. 두개 다 소인수분해 해보면 됩니다!
1112 = 139 * 2 * 2 * 2
695 = 139 * 5
그래서 1112와 695의 최대공약수는 139가 됩니다!

뭐... 695 끝자리가 5니까 5로 나누면 139가 나오기 때문에 머리로 못 구하는 건 아니지만,
컴퓨터라면 어떻게 알고리즘을 짜야될지 감이 안 올뿐더러,
수가 커지면 일일이 소인수분해해서 비교하는 데도 시간이 오래 걸릴 것이 뻔하다.

A2. 유클리드 호제법을 사용하면 됩니다!
1112 % 695 = 417
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0

약간 피보나치 수열 계산하는 느낌도 난다.

0이 나오기 직전의 수인 139가 최대공약수입니다!

Q2. 왜?

유클리드 호제법이라는게 그런 거야.

증명은 나중에 알아보도록 하자

풀이

import sys

a, b = map(int, sys.stdin.readline().rstrip().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

최소공배수는 a * b // (a와 b의 최대공약수)다.
왜냐하면, a와 b에 겹치는 소인수를 하나씩 삭제해주기 때문이다.

추가적으로, 이미 math 모듈 내에 gcd라는 함수가 내장되어 있다.

lcm 함수는 Python 3.9부터 추가되었다는데, Baekjoon의 채점 프로그램에는 lcm 함수를 인식하지 못하니 사용하지는 말자.

import math

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

print(math.gcd(a, b))
print(math.lcm(a, b))