파이썬 최대공약수와 최소공배수 알고리즘

최대공약수란 ?

• GCD (Greatest Common Divisor)
• Common Divisor → 라는 이름에서 알 수 있듯이 두 수 혹은 그 이상의 여러 수의 공통인 약수 중, 최대인 것.
• 즉, 수들의 각각의 약수 중 공통이며 가장 큰 수를 최대공약수라고 한다.
• 8 의 약수 - 1,2,4,8 10 의 약수 - 1,2,5,10 8과 10의 공통 약수 : 1,2 중 가장 큰 수 : 2 8과 10의 최대공약수 : 2

최소공배수란?

• LCM (Least Common Multiple)
  • 두 수, 혹은 그 이상의 수들의 공통인 배수 중 최소, 가장 작은 수. 즉, 수 들의 각각의 배수 중 공통이며 가장 작은 수를 최소공배수라고 한다.

  10의 배수 : 10,20,30,40,50,60,70,80,90,100,110,120,130,....
  
  12의 배수 : 12,24,36,48,60,72,84, 96, 108, 120,....
  
  10과 12의 공통 배수 : 60, 120, ... -> 공배수 중 가장 작은 것 60
  
  10과 12의 최소공배수 : 60
  
  

최대공약수 & 최소공배수 구하기

• 보통 소인수분해로 최대공약수와 최소공배수를 구할 수 있지만 파이썬을 공부하고 있으므로 파이썬 알고리즘을 기준으로 설명해보겠습니다. (일반 for문 & 유클리드 호제법)
• 먼저 for문으로 최대공약수와 최소공배수를 for 구문을 돌려 구해보면 아래와 같습니다.

최대 공약수 구하기 & 최소 공배수 구하기

a = 10
b = 12

#최대 공약수 구하기
for i in range(min(a, b),0, -1):
	if a % i == 0 and b % i == 0:
		print(i)  #2
		break 
#최소 공배수 구하기
for i in range(max(a, b),(a * b) + 1):
	if i % a == 0 and i % b == 0:
		print(i)  #60
		break

최대 공약수 구하기 설명 :

• a,b, 중 가장 작은 숫자부터 1까지 -1을 하며 for문을 실행시킵니다. 만약 a%i , b%i 값이 모두 딱 떨어져서 나머지가 없는 상태 (==0) 라면 이 때 사용된 i는 a와b의 최대 공약수입니다. (a,b를 모두 나눌 수 있는 약수 중 가장 큰 수)

최소 공배수 구하기 설명 :

• a,b 중 더 큰 숫자부터 a*b의 수까지 for문을 실행시킵니다. 더 큰 숫자부터 실행하는 이유는 a, b의 배수들 중 공통 부분을 찾는 것이기 때문에 a,b 중 작은 수부터 시작하게되면 i가 ++1이되면서 둘 중 큰수에 도달할 때까지 for문은 헛돌게 됩니다.
• i % a, i % b ==0 모두 값이 떨어지는 나머지가 없는 상태라면 이 때 사용된 i는 a와b의 최소공배수입니다.

최대 공약수는 : 공통 약수들 중 가장 큰 것을 구하는 것이므로 for구문을 주어진 수 ~ 1 까지 -1을 하며 돌렸고

최소 공배수는 : 공통 배수들 중 가작 작은 것을 구하는 것이므로 for 구문을 주어진 수 부터 +1 을 했습니다.

어디부터 시작하는건 상관없지만 최대한 빨리 찾아서 for문을 끝내는게 시간, 자원적으로 효율이 좋기 때문입니다.

유클리드 호제법

이제 그 유명한 '유클리드 호제법' 으로 최대공약수와 최소공배수를 구해보겠습니다. 최소공배수는 최대공약수를 알면 간단하게 구할 수 있습니다.

유클리드 호제법을 쉽게 설명해보면

• x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리를 이용하는 것입니다. ( x%y = r  (x를 y로 나눈 나머지값 == r))

 x와 y 최대공약수 == y와 r의 최대공약수

• 즉, 계속해서 x 에는 y값을 대입하고 y 에는 (x % y)값인 r을 대입하다보면 언젠가는 x % y == 0 일 때가 있습니다.

이 때의 y자리에 있는 2가 바로 x와 y의 최대 공약수입니다.

유클리드 호제법을 활용한 파이썬 알고리즘 ↓

#유클리드 호제법
#최대공약수 구하기
def GCD(x,y):
	while(y): #y가 참일 동안 = 자연수일 때 =   a%b!=0
		x, y = y, x % y
	return x

print(GCD(10,12))  #2

#최소공배수 구하기
def LCM(x,y):
    result = (x * y) // GCD(x,y)
	return result 

print(LCM(10,12))   #60

최대 공약수 설명

• while(y) == True 일경우 즉, y가 0 초과일 경우 (이 부분은 a%b!=0으로 수정가능) x의 자리에는 y의 값을 y의 자리에는 x%y(나머지,r) 의 값을 넣는다. 그리고 다시 while문 반복, 언젠가 (는 꼭 온다) y가 0이 될 때 , 즉 x를 y로 나누어 떨어질 때 그 y의 값은 x,y의 최대공약수이다.

최소 공배수 설명

• x * y를 최대공약수로 나눈 몫이 ⇒ 최소공배수이다
• 10, 12의 최대공약수 : 2
  • 10 * 12 // 2 ⇒ 60
  • 10, 12의 최소공배수는 60