[python] 최대공약수와 최소공배수 클래스 만들기

최대공약수와 최소공베수 클래스 만들기

• 두 수의 최대공약수
• 두 수의 최소공배수
• 최대공약수와 최소공배수의 클래스 구현

두 수의 최대공약수

다음 함수로 두 수의 공약수를 결정할 수 있습니다.

def commomFactor(x, y):
    re=[1]
    if x < y :
        smaller=x
    else:
        smaller=y
    for i in range(2, smaller+1):
        if (x % i ==0) and (y %i==0):
            re.append(i)
    return(re)

commomFactor(54, 24)

[1, 2, 3, 6]

두 수의 최대공약수는 사용자 정의함수 commomFactor()의 결과 중 최대수를 반환하는 방식으로는계산할 수 있습니다. 이러한 방식은 큰 수 일수록 반복문의 횟수가 증가합니다. 이러한 문제는 유클리드 호제법을 적용하여 개선할 수 있습니다. 즉, 두 수 a, b 로부터 다음 알고리즘에서 a%b=0이 될 때까지 반복하면 a가 최대공약수가 됩니다.

a, b = b, a % b

예를들어 76, 24의 최대공약수의 계산과정은 다음과 같습니다.

a, b=76, 24
a, b=b, a%b
a, b

(24, 4)

a, b=b, a%b
a, b

(4, 0)

위 결과와 같이 최대공약수는 a%b=0인 경우의 a 값인 4입니다. 그러나 유클리드 호제법으로 3, 5에 대한 최대공약수는 1이 반환됩니다.

a, b=3, 5
while True:
    a, b=b, a%b
    a, b
    if a%b == 0:
        break
a=b
a    

1

그러므로 위 상황을 고려하여 유클리드호제법을 사용하는 함수는 다음과 같이 작성할 수 있습니다.

def gcd(x, y):
    x1=[x, y]
    while(y):
        x, y=y, x%y
    if x ==1 :
        x=x1[0]*x1[1]
    return x

gcd(76, 24)

4

gcd(3, 5)

15

두 수의 최소공배수

공배수는 각 수의 배수들 중 공통인 수를 의미합니다. 그 공배수 중 가장 작은 값을 최소공배수라고 하며 다음과 같이 계산할 수 있습니다.

\begin{align} a = 24,& \quad b = 76\\ 2&\vert \underline{24\quad 76}\\ 2&\vert \underline{12\quad 38}\\&\;\; 6\quad 19\\ \text{gcd}:\;&2\times 2=4\\ \text{lcm}:\;&2\times 2 \times 6 \times 19 =\frac{24 \times 76}{4} =456\\ \therefore \;& \text{lcm} =\frac{a \times b}{\text{gcd}} \end{align}

def lcm1(a, b):
    if a>b:
        greater=a
    else:
        greater=b
    while(True):
        if (greater % a == 0) and (greater % b ==0):
            re = greater
            break
        greater +=1
    return(re)

lcm1(3,5)

15

lcm1(24, 76)

456

위 lcm1() 함수와 같이 두 인수에 대한 직접적인 계산은 인수의 크기가 클수록 계산 반복의 증가로 실행시간은 증가됩니다. 대신에 위 식에서 나타낸 것과 같이 두수의 최대공약수를 활용하여 실행시간의 단점을 극복할 수 있습니다. 다음 함수 lcm2()는 내재된 최대공약수 함수를 사용합니다.

def lcm2(a, b):
    def gcd(x, y):
        x1=[x, y]
        while(y):
            x, y=y, x%y
        if x ==1 :
            x=x1[0]*x1[1]
        return x
    if a*b == gcd(a, b):
        re=a*b
    else:
        re=a*b/gcd(a, b)
    return(re)

lcm2(24, 76)

456.0

lcm2(3, 5)

15

최대공약수와 최소공배수의 클래스 구현

정적메서드(Static method)와 클래스메서드(Classmethod)를 적용하였습니다.

class gcdLcm:
    @staticmethod
    def gcd(x, y):
        x1=[x, y]
        while(y):
            x, y=y, x%y
        if x ==1 :
            x=x1[0]*x1[1]
        return x
    @classmethod
    def lcm(clf, a, b):
        if a*b == gcdLcm.gcd(a, b):
            re=a*b
        else:
            re=a*b/gcdLcm.gcd(a, b)
        return(re)

gcd(3, 5)

15

A=gcdLcm()
A.lcm(24, 76)

456.0

gcdLcm.lcm(3, 5)

15