[Python] 최소공배수, 최대공약수란? 파이썬 알고리즘으로 쉽게 구현하기 / for문, 유클리드 호제법 이용

최대공약수란 ? 

GCD (Greatest Common Divisor) 

Common Divisor -> 라는 이름에서 알 수 있듯이 두 수 혹은 그 이상의 여러 수의 공통인 약수 중, 최대인 것. 

즉, 수들의 각각의 약수 중 공통이며 가장 큰 수를 최대공약수라고 한다. 

ex) 

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 를 최대공약수로 나눈 몫이 == 최소공배수이다. 

ex) 10, 12의 최대공약수 : 2 

10 * 12 // 2 => 60

10, 12의 최소공배수는 60 

 

 

 

 

 

---

 

 

 

위 포스팅을 쓴 후 며칠 지나서 알게된 math 함수로 최대공약수, 최소공배수 한방에 구하는 법 !! 이 있었다. 

ㅠㅠ 이렇게 간편한 것을,,,,,,,,,,,

https://codingpractices.tistory.com/46

[Python] math.gcd & math.lcm 최대공약수 최소공배수 한번에 쉽게 구하기