[프로그래머스] Level1 최대공약수와 최소공배수(with python)

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

프로그래머스

 

1. 내가 작성한 코드

def solution(n, m):
    arr = []
    
    for i in range(min(n,m),0,-1):
        if n%i == 0 and m%i == 0:
            arr.append(i)
            break

    for i in range(max(n,m),n*m+1):
        if i%n == 0 and i%m == 0:
            arr.append(i)
            break
            
    return arr

유클리드 호재법이 잘 기억 안나서 그냥 정석으로 풀었다 ㅜㅜ 

 

구글링해서 다시 적어보는 유클리드 호재법 활용

 

2. 유클리드 호재법

def solution(n,m):
    c,d = max(n,m), min(n,m)
    t = 1
    while t>0:
        t = c % d
        c,d = d,t
    
    return (c, int((n*m)/c))

 

gcd(최대공약수) => 한 수가 0이 될 때까지 나눔 => 그 나눈 수가 최대공약수

 

ex)

max => 5, min => 2

5,2 => 2(=min),1 => 1,0  (하나의 수가 0이 됐기 때문에 최대공약수는 1)

 

lcm(최소공배수) => 주어진 두 수를 곱한 후 최대공약수로 나눈 수