#2609 최대공약수 최소공배수 [백준](H99.16)

📄문제

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

예제 입력1

24 18

예제 출력1

6
72

🖋️코드

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

def gcd(a, b):
    if a > b:
        while b > 0:
            a , b = b , a % b
        return a
    else:
        while a > 0:
            b , a = a , b % a
        return b

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(a, b))
print(lcm(a, b))

🧷(나만 알아듣는) 추가설명

처음에는 각 숫자의 공약수들을 따로 list로 담아서 공집합으로 같은것중 가장 높은 수를 프린트 하는 방식을 사용했지만 효율적이지 않은거 같다.
"유클리드 호제법" 으로 풀면 간단해진다.
a를 b로 나눈 나머지를 c 이라고 했을 때, a와 b의 최대공약수는 b와 c의 최대공약수이다.
즉, a와 b의 최대공약수는 b와 a%b의 최대공약수이다. (신기..)
그리고 최소공배수는 a * b / 최대공약수이다. (더 신기..)