[파이썬] 유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기

[파이썬] 유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기

---

 

유클리드 호제법

A>B일때, A%B를 R이라고 할때,

A와 B의 최대공약수와 B와 R의 최대공약수가 같다는 원리이다.

 

A에 B를 대입하고 B에 R을 대입하는 과정을 반복하다보면 R=0이 되는 상황이 생기는데, 이때 B자리에 위치한 숫자가 바로 A와 B의 최대 공약수가 된다.

 

def GCD(x, y):
    while y:
        x, y = y, x%y
    return x
print(GCD(10, 12))

2

 

y가 0이 아닌 수일때(참일 때) x, y = y, x%y는 계속해서 반복된다.

x % y == 0이 되는 순간에 x%y은 y에 대입되므로 반복문의 조건을 만족하지 못해 빠져나오게 된다.

x에는 y의 값이 대입되었으므로 x값을 반환함으로써 최대공약수를 얻을 수 있다.

 

이렇게 얻어낸 최대공약수를 이용하면 최소공배수를 쉽게 구할 수 있다.

x*y를 최대공약수로 나눈 몫이 최소공배수가 되기 때문이다.

 

def GCD(x, y):    # 최대공약수
    while y:
        x, y = y, x%y
    return x

def LCM(x,y):    # 최소공배수
    return (x*y) // GCD(x,y)

print(GCD(10, 12), LCM(10, 12))

2 60

 

 

파이썬에 내장된 math 라이브러리를 이용하면 더욱 간단하게 최대공약수와 최소공배수를 구할 수 있다.

import math
print(math.gcd(10, 12, 18))    # 최대공약수
print(math.lcm(10, 12, 15))    # 최소공배수

2 60

기본적으로 여러개의 인자값을 받을 수 있으나 온라인 파이썬 프로그램 환경에서는 인자값을 2개까지만 받는 경우가 있다고 한다.