[Algorithm/Python] 파이썬 최대공약수와 최소공배수 구하기 ( 유클리드 호제법 )

문제

n, m 두 개의 자연수가 주어졌을 때, 최대공약수와 최소공배수를 구하기

 

풀이

math 모듈의 gcd 함수 사용하기

from math import gcd

def lcm(a,b) :
    return a*b // gcd(a,b)

print(gcd(n,m), lcm(n,m))

• math 모듈의 gcd 함수를 사용한다면 바로 최대공약수를 알아낼 수 있다.
• 최소공배수는 [ 두 수의 곱 / 두 수의 최대공약수 ] 로 표현할 수 있다.

 

최소공배수를 구하는 것에 대해 이해가 잘 가지않아서 예시를 들어서 표현해보겠다.

 

Ex ) n = 24, m = 18

 

이때, 최소공배수는 2*3 = 6 , 최대공약수는 2*3*4*3 = 72 가 나오게 된다.

최대공약수의 식에서 뒤에 있는 4와 3에 집중해야 한다. 4가 나온 경로를 보면 24 / 2 / 3 의 과정이고 3은 18 / 2 / 3 으로 값이 나오게 된다.

그러므로 2 * 3 * (24 / (2 * 3)) * (18 / (2 * 3)) 으로 표현할 수 있다. 2 * 3 * (24 / (2 * 3)) * (18 / (2 * 3)) 로 표현할 수 있고 이렇게 된다면 24 * 18 * (2 / 3) 즉, 두 수의 곱 / 두 수의 최대공약수 로 표현이 되는 것이다..!

(깨닫고 혼자 소름)

 

최대공약수 직접 구현(유클리드 호제법)

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

def lcm(a,b):
    return a*b // gcd(a,b)

print(gcd(n,m), lcm(n,m))

• 유클리드 호제법을 이용한 풀이이다.
• 유클리드 호제법은 a, b의 최대공약수와 b, r(a%b의 나머지) 의 최대공약수가 같다는 성질을 이용한 풀이이다.
• 계속 계산을 반복해 나머지가 0이 될 때까지 계산한다.
• ex) (24, 18의 최소공약수) = (18, 6의 최소공약수) = (6, 0의 최소공약수) = 6

 

관련 문제

2609번: 최대공약수와 최소공배수

 

---

 

자주 풀어도 가끔 까먹는 문제...

사실 최소공배수 이해 잘 안 됐었는데

다시 한번 해보니깐 잘된다 반복학습 good

@미닛메이드 Minnit