파이썬(Python) 최대공약수와 최소공배수

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

 

1. 최대공약수

두 수 X와 Y가 있을 때, X의 약수이면서 Y의 약수인 수(공약수) 중 최대값을 가진 값을 최대공약수라고 합니다.
우리가 초등학교 시절에 배웠던 방법은 아래와 같습니다.
12와 16의 공약수를 어림잡아 나눠 맨 왼쪽의 숫자들을 곱한게 최대공약수입니다.

두 수의 최대공약수 구하는 방법

위의 방식을 봤을 때 다음과 같은 정의가 내려집니다.

X와 Y를 어떠한 미지수 A로 나눴을 때 0이 되는 최대값을 구하면 됩니다.

예를 들어, num1이라는 변수에는 12, num2라는 변수에 16이라고 가정하고 파이썬으로 코드를 구현한 것은 다음과 같습니다.

#num1과 num2의 최대공약수 구하기
num1 = 12
num2 = 16
for i in range(num1+1,1,-1):
    if num1%i==0 and num2%i==0:
        print(i)
        break #탐색 종료

 

여기서, for문을 1부터 돌리게 되면 최소공약수가 출력이 되기에 두 수 중에 가장 작은수부터 1까지 -1 감소를 시켜 for문을 돌리게 되면 최대공약수를 구할 수 있습니다.

위의 코드를 함수로 구현을 한다면 아래와 같습니다.

#최대공약수 함수
def GCD(X, Y):
    if X<Y:
        min = X
    else:
        min = Y
    for i in range(min+1,1,-1):
        if X%i==0 and Y%i==0:
            res = i
            break
    return res

 

이 방법에 더해서 유클리드 호제법을 이용하여 최대공약수를 구할 수 있습니다.
유클리드 호제법은 다음과 같습니다.

def UC(X, Y):
    while(Y):
        X, Y = Y, X%Y
    return X

 

2. 최소공배수

두 수 X와 Y가 있을 때, X의 배수이면서 Y의 배수인 수(공배수) 중 최솟값을 가진 값을 최소공배수라고 합니다.
우리가 초등학교 때 썼던 최소공배수 구하는 방법은 아래와 같습니다.

최소공배수 구하는 방법

최소공배수를 구하는 방법은 두 수 중에서 최댓값부터 for문을 돌려 범위는 두 수를 곱한 범위까지 i를 num1과 num2로 나눴을 때 0이 되면 출력해도 좋습니다. 

#for문을 이용한 최소공배수 파이썬 코드
num1 = 12
num2 = 16
for i in range(num2,(num1*num2)+1):
    if i%num1==0 and i%num2==0:
        print(i)
        break

 

위의 방법뿐만 아니라, while문을 만들어 최댓값부터 i를 num1과 num2로 나눠 0이되는 순간에 break를 걸어 while문을 종료해도 됩니다.

num1 = 12
num2 = 16
i=num2 #최댓값을 i에 저장
while(True):
    if i%num1 ==0 and i%num2==0:
        print(i)
        break
    i+=1

 

위의 코드를 함수로 구현을 한다면 아래와 같습니다.

#최소공배수 함수
def LCM(X, Y):
    if X<Y:
        max = Y
    else:
        max = X
    for i in range(max,(X*Y)+1):
        if i%X==0 and i%Y==0:
            res = i
            break
    return res

 

3. 최대공약수와 최소공배수 관계

유클리드 호제법을 활용하여 최소공배수를 쉽게 구할 수 있습니다.
예를 들어, X = AB, Y = BC라고 했을 때 X와 Y의 최대공약수는 B, 최소공배수는 ABC입니다.
X와 Y를 곱하면 AB^2C이니까 최대공약수 B로 나누면 최소공배수 ABC가 나옵니다.
위의 유클리드 호제법을 이용한 최대공약수를 구하는 코드는 아래와 같습니다.

#유클리드 호제법을 이용한 최대공약수 구하기
def UC(X, Y):
    while(Y):
        X, Y = Y, X%Y
    return X

#유클리드 호제법을 이용한 최소공배수 구하기
def UC2(X, Y):
    result = (X*Y) // UC(X,Y)
    return result