[Programmers]Lv 1. 최대공약수와 최소공배수

문제:

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

풀이 방법:

 최대공약수를 구하는 방법중 가장 좋은 방법은 유클리드 호제법을 사용하는 것이다. 작은 수의 경우에는 상관 없으나 문제와 같이 수가 커질 경우에는 유클리드 호제법이 효율적이기 때문이다. 

 유클리드 호제법이란 '정수 a,b,q,r(b!=0)에 대하여 a=bq+r이면 G(a,b)=G(b,r)가 성립한다.'라는 것이다. 따라서 이를 이용해 b가 0이 될 때가 while문을 반복하도록 해서 최대공약수를 구하도록 하였다.

최소공배수는 두 수의 곱에다가 최대공약수를 나누면 쉽게 구할 수 있다.

def solution(n, m):
    gcd=n
    multi=n*m
    while m !=0:
        gcd,m=m,gcd%m
    lcm=multi/gcd
    answer = [gcd,int(lcm)]
    return answer