[항해]알고리즘 스터디(백준 #2609)

백준#1037 - 최대공약수와 최소공배수

바로가기

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

입출력 규칙
1. 입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
2. 출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

문제 접근
1. 입력은 1줄이다. 입력받은 수를 각각 a, b로 지정해 연산을 하기 위한 방법으로는 map(int, input().split(" ")) 또는 num = input().split(" ") -> a = int(num[0]), b = int(num[1])
2. GCD(Greatest Common Divisor, 최대공약수)를 구하기 위해 호제법을 사용한다.
2-1.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
3. LCM(Least Common Multiple, 최소공배수) 최소공배수는 a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.

코드

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


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

    return a


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


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