[프로그래머스] Lv1 - 최대공약수와 최소공배수 (파이썬)

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

코딩테스트 연습 - 최대공약수와 최소공배수

 

def solution(n, m):
    answer = []
    for i in range(n, 0, -1):
        if n % i == 0 and m % i == 0:
            answer.append(i)
            break
    return answer+[n*m//answer[0]]

 

풀이
1.  (i = n~1) n과 m이 i로 나누어 떨어지면 최대공약수
2. 두 수의 곱을 최대공약수로 나눈 값은 최소공배수
3. 배열로 출력

 

다른 풀이

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

def solution(n, m):
    a, b = sorted([n, m], reverse=True)
    r = 1
    while r > 0:
        r = a % b
        a, b = b, r
    answer = [a, n*m//a]
    return answer

풀이
1. a, b = n, m 중 최대 최소 값
2. (r = 나머지) r이 0일 때까지 : 유클리드 호제법
    - r = a%b
    - a, b = n, r
3. 두 수를 최대공약수로 나눈 값은 최소공배수
4. answer 리턴

---

유클리드 호제법이라니 생각도 못했다...

프로그래머스에는 천재들만 있는 것 같다