[백준] 2609 - 최대공약수와 최소공배수

문제

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

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

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

입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 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을 반환하는 재귀함수이다.

 

유클리드 호제법을 이용한 최소공배수 구하기!

두 수를 곱한 값을 두 수의 최대공약수로 나누면 최소공배수가 된다.