[프로그래머스] 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

---

용어 정리

 - 약수: 어떤 수를 나누어떨어지게 하는 수

 - 공약수: 두 개 이상의 수에서 공통된 약수

 - 최대공약수: 공약수 중 가장 큰 수

 - 공배수: 두 개 이상의 수에서 공통된 배수

 - 최소공배수: 공배수 중 최솟값

 

최대공약수(greatest common divisor) 구하기

1) 약수를 모두 구한 후 그중 최대값을 찾는다.

 

2) 공통된 소인수의 거듭제곱 중 지수가 작은 수를 모두 곱한다.

 

3) 유클리드 호제법으로 구할 수 있다.

 - x와 y 의 최대공약수는 y와 r의 최대공약수와 같다. (r = x%y)

 - r이 0이 될때까지 계속해서 나누었을 때, 마지막 y값이 최대공약수이다.

 

 

최소공배수(least common multiple) 구하기

1) 공통인 소인수의 거듭제곱에서 지수가 큰 수와, 공통되지 않은 수를 모두 곱한다.

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

 

---

제출 코드

def GCD(a,b):
    if a % b == 0:
        return b
    else:
        return GCD(b, a%b)

def LCM(a,b):
    return a * b // GCD(a,b)

def solution(n, m):
    if n < m:
        n, m = m, n
    return [GCD(n,m), LCM(n,m)]