[Py_Lv1] 대공약수와 최소공배수

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

접근법

최대공약수와 최소공배수를 구하는 방법 중 유클리드 호제법을 사용했다.

주어진 2개의 수준 가장 큰 수를 작은 수로 나누고 그 나머지로 작을 수를 다시
나누는 과정 반복하여 나머지가 0이되는 순간에 나누는 값을 최대 공약수가 되는 것이다.

이렇게 구해진 최대 공약수는 주어진 두 수 n, m을 이용해 최소 공배수를 구할 수 있다.

n m = 최대 공약수 최소 공배수라는 공식에 대입함으로 쉽게 구해진다.

그 과정을 아래의 코드로 작성하여 문제를 해결하였다.

나중을 위해 이러한 공식은 꼭 외우고 넘어가야겠다.

===========================================================

def solution(n, m):
    answer = []
    num = max(n,m)
    div = min(n,m)
    
    while (num % div != 0):
        re = num % div
        
        num = div
        div = re
    
    answer.append(div)
    answer.append((n * m) / div)
    return answer