(Python)최대공약수(GCD)와 최소공배수(LCM) 구하기

최대공약수(GCD)와 최소공배수(LCM)  구하기

최대공약수(GCD)

최대공약수: 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값.

 

최소공배수(LCM)

최소공배수: 두 자연수들의 배수들 중에서 공통된 가장 작은수를 말한다. 

최소공배수는 최대공약수를 구했다면 최소공배수는 한 층 구하기 쉽다. 

최소공배수 = 두 자연수의 곱 / 최대공약수 

이기때문이다. 

 

유클리드 호제법을 사용하여 두 값을 구할 수 있다. 

2개의 자연수 a,b에 대하여 a를 b로 나눈 나머지를 r이라고 하면 (단, a>b) ,

a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 

 

따라서 정리하면, b를 r로 나눈 나머지 r'를 구하고 , 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을때 나누는 수가 a와 b의 최대공약수이다.