[Python] 약수와 소인수분해를 이용한 최대공약수 구하기

두 수 X와 Y의 최대공약수를 어떻게 구할 수 있을까? 

 

1. X와 Y의 모든 약수를 구한 다음 공통되는 약수 중 가장 큰 수를 찾아내면 된다.

 

2. X와 Y를  소인수분해한 다음 공통되는 인수를 모두 곱해서 구한다.

 

 

-1번 방법

def divisors(n):  
    div = []  
    for i in range (1, n + 1):
        if (n % i == 0):
            div.append(i) 
    return div 

def commons(n, m):
    comm = []
    for i in n:
        if(i in m):
            comm.append(i)
    return comm

def gcd(n, m):
    div_n = divisors(n)
    div_m = divisors(m)
    comm = commons(div_n, div_m)
    return comm[len(comm) - 1]

x = 78696
y = 19332

g = gcd(x, y)
print('최대공약수는', g)

 

우선 n의 약수를 구해주는 divisors 함수를 정의하고, 두 약수 list에서 공통된 수를 뽑아 공통 약수 list를 만드는 commons 함수를 정의한 후,  gcd 함수를 이용해 약수 list의 가장 마지막 수(가장 큰 약수 = 최대공약수)를 구할 수 있다.

 

-2번 방법

def factorize2(n):
    factor = 2
    factors = []
    while (factor ** 2 <= n):
        while(n % factor == 0):
            n = n // factor
            factors.append(factor)
        factor += 1
    if (n > 1):
        factors.append(n)
    return factors

def commonFactors (n, m):
    i = 0
    j = 0
    commons = []
    while (i < len(n) and j < len(m)):
        if (n[i] == m[j]):
            commons.append(n[i])
            i += 1
            j += 1
        elif (n[i] < m[j]):
            i += 1
        else:
            j += 1
    return commons

def gcd2(n, m):
    f1 = factorize2(n)
    f2 = factorize2(m)
    factors = commonFactors(f1, f2)
    gcd = 1
    for i in factors:
        gcd *= i
    return gcd
    
x = 78696
y = 19332
g = gcd2(x, y)
print('최대공약수는', g)

 인수를 구해주는 factorize2 함수를 정의하고, 공통적인 인수들을 묶어주는 commonFactors 함수를 정의한 이후 gcd2를 이용해 공통 인수를 전부 곱하여 최대공약수를 구한다.