[백준] Bronze 1. 2609 - 최대공약수와 최소공배수 python

문제 링크

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

---

문제 설명

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

 

입력

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

 

출력

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

---

제출 코드

import sys

input = sys.stdin.readline

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
    
def lcd(a, b):
    return abs(a*b) // gcd(a, b)

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

print(gcd(a, b))
print(lcd(a, b))

 

풀이

• 유클리드 호제법을 이용하여 최대공약수를 먼저 구한다.
• 두 수의 곱을 최대공약수로 나누면 최소공배수 이다.

 

알아둘 사항

2024.07.15 - [coding test/알고리즘] - [python] 최대공약수 / 최소공배수 - 유클리드 호제법

[python] 최대공약수 / 최소공배수 - 유클리드 호제법