문제
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
예제입력 1
24 18
예제 출력 1
6
72
풀이
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
def gcd(n,m):
if n%m == 0:
return m
else:
return gcd(m, n%m)
print(gcd(n,m))
print((n*m)// gcd(m,n))

설명
아 제일 기초가 되는 알고리즘인데 까맣게 잊어버렸다....ㅠㅠㅠ
** 유클리드 호제법
유클리드 호제법: 두 자연수 a, b에 대해 (a>b) a를 b로 나눈 나머지를 r 이라고 할 때 a,b 의 최대공약수는 b와 r 의 최대공약수와 같다.
두 수 중 큰 수를 작은 수로 나눴을 때 나머지가 0이 되면 이것이 최대공약수 인데 만약에 나누어 떨어지지 않는다면 b 와 a를 b로 나눈 나머지인 r을 반환하는 재귀함수이다.
유클리드 호제법을 이용한 최소공배수 구하기!
두 수를 곱한 값을 두 수의 최대공약수로 나누면 최소공배수가 된다.
'Coding Test > Python' 카테고리의 다른 글
| [백준] 수 이어 쓰기 1 (0) | 2023.09.15 |
|---|---|
| [백준] 9095 - 1, 2, 3 더하기 (0) | 2023.09.13 |
| [백준] ABCDE (1) | 2023.09.03 |
| [프로그래머스] 여행경로 (lv.3) (0) | 2023.08.28 |
| [프로그래머스] 아이템 줍기 (lv.3) (0) | 2023.08.24 |