[Python] 유클리드 호제법

2022/09/06 프로그래머스_연습문제_N개의 최소공배수(문제 링크)

프로그래머스

깃 허브 풀이(깃허브 링크)

GitHub - EunGyeongKim/TIL: Today I Learne

 

---

프로그래머스 문제를 풀다가 유클리드 호제법을 이용하여 최소 공배수(LCM, Least Common Multiple)를 구하는 방법을 알게 되어 정리합니다.

---

최소 공배수, 최대공약수

먼저 간단하게 최소 공배수와 최대 공약수를 정리하겠습니다.

 

최대공약수(GCD)은 두 수 사이의 공약수 중 최대인 수를 가리킵니다.

최소공배수(LCM)은 양의 공배수 가운데 가장 작은 한 수를 가리킵니다.

 

위 그림을 참고하면 이해가 쉽습니다. 

 

24의 공약수는 2, 3, 4, 6, 8, 12가 되며, 30의 공약수는 2, 3, 5, 6, 10, 15가 됩니다. 

이 두 공약수 중 공통된 수는 2, 3, 5, 6 이며 최대값은 6이기 때문에 최대 공약수는 6이 됩니다. 

또한, 24의 배수는 24, 48, 72, 96, 120 ... 이며, 30의 배수는 30, 60, 90, 120 .... 입니다.

그러므로 이 두 수의 최소 공배수는 120이 됩니다.

 

---

 

유클리드 호제법

유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나

 

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘입니다.

 

예를들어 1071과 1029의 최대공약수를 구하는 순서는 다음과 같습니다.

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42는 21로 나누어 떨어진다. 따라서, 최대공약수는 21이다.

 

python 소스코드로 나타내면 다음과 같습니다.

#최대 공약수
def gcd(a,b):
    c = 0 
    while (b!=0):
        c = a%b
        a, b = b, c
    return a

---

<추가>

만약 최소 공배수를 구하고 싶다면

lcm = (a*b) / gcd(a,b)

를 해주면 된다!