[백준] 2609 - 최대공약수와 최소공배수(브론즈 1)

---

1트

재귀로 풀 수 있는 것은 반복문으로도 풀어보자

최대 공약수 greatest common divisor
최소 공배수 leaest[lowest] common multiple

최대 공약수는 유클리드 호제법으로 구한다.
직접 구해도 되지만 그런 경우는 시간 복잡도가 log(n^2)이다.(1 ~ n/2까지 구해봐야 하니까)

최소 공배수는 두 수 n, m이 있을 때, 두 수 n, m 을 곱하고 그 결과를 두 수 n, m의 최대 공약수로 나눈 수이다.

Python의 경우 내장 라이브러리인 math를 통해서 구할수도 있다.

import math

gcd = math.gcd(10, 20)
lcm = math.lcm(10, 20)


gcd = math.gcd(10, 20, 25)
lcm = math.lcm(10, 20, 25)

유클리드 호제법

자연수 a, b가 있을 때 a > b라고 가정하자.

1. a % b 의 값을 구한다. (a를 b로 나눈 나머지 값을 구한다.)
2. 두 가지 경우

• a % b 의 값이 0인 경우
  b가 최대 공약수다.
• a % b 의 값이 0이 아닌 경우
  a = b, b = a % b (a에 b의 값을 넣고 , b에 a를 b로 나눈 나머지 값을 넣는다.)

3. 1-2 단계를 반복한다.

# greatest common divisor
# 디바^이져
def get_gcd(num1, num2):
    if num1 > num2:
        a, b = num1, num2
    else:
        a, b = num2, num1

    while b != 0:
        remainder = a % b
        a = b
        b = remainder
    return a


def get_gcd_by_recursive(num1, num2):
    if num1 > num2:
        return __get_gcd_by_recursive(num1, num2)
    else:
        return __get_gcd_by_recursive(num2, num1)


def __get_gcd_by_recursive(num1, num2):
    if num2 == 0:
        return num1
    return get_gcd_by_recursive(num2, num1 % num2)


# least common multiple
# lowest common multiple
# 최소 공배수는 두 수 n, m을 곱하고 n,m의 최대 공약수로 나눈 값과 같다.
def get_lcm(num1, num2):
    gcd = get_gcd(num1, num2)
    return int(num1 * num2 / gcd)


num1, num2 = map(int, input().split())

print(get_gcd_by_recursive(num1, num2))
print(get_lcm(num1, num2))