2609 - 최대공약수와 최소공배수

최대공약수 GCD(Greatest Common Divisor)

최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

ex) 72 와 30의 최대공약수는 6이다.

 

최소공배수 LCM(Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

최소공배수 = 두 자연수의 곱 / 최대공약수

ex) 72 와 30의 최소공배수는 360이다.

 

유클리드 호제법(Euclidean Algorithm)

2개의 자연수를 받아 최대공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다.

위와 같은 방법으로 문제를 풀면 시간복잡도는 O(N)이 된다. 나쁜 방법은 아니지만 효율을 높이기 위해 유클리드 호제법이란 알고리즘을 사용하면 시간복잡도를 O(logN)으로 줄일 수 있다.

유클리드 호제법 수식

 

72와 30의 최소공배수를 유클리드 호제법을 이용해 구하는 예시

위 표에 땨라서 유클리드 호제법에 의해 해당 순서대로  A%B가 0이되는 순간 B의 값 6이 최소공배수가 된다.

---

처음에는 그냥 GCD 함수 하나 만들어서 이 함수만으로 최소공배수까지 구하려고 했지만 풀다보니까 오히려 더 복잡해지는 느낌이 들어서 그냥 LCM 함수도 하나 더 추가해서 구현했다.

GCD, LCM 두 함수 모두 재귀를 이용했고, 각 함수 이름에 맞는 결과를 도출 할  수 있도록 코드를 작성했다.

# 최대공약수
def GCD(A, B):
    if A%B == 0:
        return(B)
    return GCD(B, A%B)

# 최소공배수
def LCM(a, b):
    return a * b // GCD(a, b)

a ,b = map(int,input().split())
print(GCD(a, b))
print(LCM(a, b))