python - 최대공약수 구하기

공약수는 두 개 이상의 자연수가 공통으로 갖는 약수입니다.

예를 들어 4의 약수는 1,2,4, 6의 약수는 1,2,3,6입니다. 공약수는 1,2입니다. 최대공약수는 공약수들 중 가장 큰 수인 2입니다.

참고로 서로소란 최대공약수가 1인 두 자연수를 서로소라고 합니다. 3과 4는 최대공약수가 1입니다. 그러므로 3과 4는 서로소입니다.

 

python에서 최대공약수를 구할 때 gcd함수를 이용할 수 있습니다.

>>> from math import gcd
>>> gcd(4, 6)
2

 

유클리드 호제법을 이용하여 gcd를 직접 구현할 수 있습니다.

def gcd_my(a, b):
    if b == 0:
        return a
    else:
        return gcd_my(b, a % b)

 

배열의 숫자들의 최대공약수를 구하고 싶다면 다음과 같은 함수를 구현해 볼 수 있습니다.

def gcd_array(arr):
    gcd_arr = None
    for i in range(len(arr)):
        if i == 0:
            gcd_arr = arr[i]
        else:
            gcd_arr = gcd(gcd_arr, arr[i])
    return gcd_arr

첫 번째 두 번째 숫자의 최대공약수를 구하고, 최대공약수와 세 번째 숫자의 최대공약수를 구하고, 최대공약수와 n번째 숫자의 최대공약수를 구하는 방식으로 반복문을 돌리면 됩니다.