최대공약수, 최소공배수 구하기 (유클리드 호제법)

N과 M의 숫자가 주어졌을 때,

 

- 최대공약수(GCD)

--> 유클리드호제법

: N(=큰수), M(=작은수) 가 있을 때 N%M를 X라고 한다.

X가 0이 아니면 M%X 를 수행하고,,, 나머지가 0일 때까지 반복한다.
나머지가 0이 되었을 때 n%m 의 m 값이 최대공약수가 된다.

 

- 최소공배수(LCM)

--> 최대공약수를 통한 계산

: N = ab, M = bc 일때,

최대공약수는 b, 최소공배수는 abc 이다.

이 때 최소공배수는 NM (=ab^2c) 에서 최대공약수(b) 를 나눈 값과 같다.

 

 

[Python코드]

def solution(N, M):
    
    # 최대공약수 (gcd)
    ### 유클리드 호제법
    ### N(=큰수), M(=작은수) 가 있을 때 N%M를 X라고 한다.
    ### X가 0이 아니면 M%X 를 수행하고,,, 나머지가 0일 때까지 반복한다.
    ### 나머지가 0이 되었을 때 n%m 의 m 값이 최대공약수가 된다.
    n, m = max(N, M), min(N, M)
    gcd = 0
    while True :
        if n % m == 0:
            gcd = m
            break
        else:
            n, m = m, n % m
    
    # 최소공배수 (lcm)
    ### 숫자 N, M 를 곱한 값에서 최대공약수를 나눈 값
    ### N = a*b, M = b*c 라고 했을 때, 
    ### 두 수의 최대공약수는 b이고, 최소공배수는 a*b*c
    lcm = N * M / gcd
    
    
    
    # answer = [최대공약수, 최소공배수]
    answer = [gcd, lcm]
    return answer