728x90
문제 설명
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력 1
24 18
예제 출력 1
6
72
풀이
a, b = map(int, input().split())
def gcd(a, b):
if b == 0:
return a
return gcd (b, a % b)
gst = gcd(a, b)
lst = a * b // gst
print(gst)
print(lst)
- 유클리드 호제법을 사용하여 문제를 해결한다.
- 유클리드 호제법을 통해 최대공약수를 구할 수 있고, 'a * b / 최대공약수' 식을 통해 최소공배수를 구할 수 있다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 / 정수론] 14565 : 역원(Inverse) 구하기 (python) (0) | 2024.04.08 |
---|---|
[백준 / 정수론] 11689 : GCD(n, k) = 1 (python) (0) | 2024.04.08 |
[백준 / 정수론] 1978 : 소수 찾기 (python) (0) | 2024.04.08 |
[백준 / 소수] 1456 : 거의 소수 (python) (0) | 2024.04.05 |
[백준 / 그리디] 2839 : 설탕 배달 (python) (0) | 2024.04.04 |