최대 공약수와 유클리드 알고리즘 (with Python3)

최대공약수 구하기

1을 제외한 공통 약수 중 최댓값을 최대 공약수(Greater common factor)라고 한다.

 

예를들어, 4 와 6 의 최대공약수는 2 이다.

15와 40의 최대 공약수는 5 이다.

 

최대 공약수는 두 수 중 작은 수보다 클 수 없다. 따라서 초기값을 두 수중 작은 값으로 하여 1씩 감소하면서 두 수를 나눴을때 나머지가 없는지 확인한다.

 

예를들어,

1. 4와 6 중 4가 작다.
2. 4와 6을 4로 나눈다. (4는 나누어 떨어지지만, 6은 나누어 떨어지지 않는다)
3. 3으로 나눈다. (4는 나누어 떨어지지 않는다, 6은 나누어 떨어진다)
4. 2로 나눈다. (둘 다 나누어 떨어진다)
5. 따라서 2가 최대 공약수이다.

 

Python 코드

아래 코드는 unittest 기반으로 작성했다. 주요 로직은 gcd() 메소드만 참고하면 된다.

# -*- coding: utf-8 -*-

import unittest


class Exam05(unittest.TestCase):
    """최대 공약수 구하기"""

    @staticmethod
    def gcd(a, b):
        i = min(a, b)
        while True:
            if i <= 1:
                return -1

            if a % i == 0 and b % i == 0:
                return i

            i -= 1

    def test1(self):
        self.assertEqual(2, self.gcd(4, 6))
        self.assertEqual(14, self.gcd(14, 98))
        self.assertEqual(3, self.gcd(15, 99))


if __name__ == "__main__":
    unittest.main()

 

유클리드 알고리즘

더 간단하고 시간복잡도도 줄일 수 있는 방법이 유클리드 알고리즘(Euclid Algorithm)을 이용하는 방법이다.

유클리드 알고리즘은 말 그래도 유클리드가 발견한 알고리즘으로, 최대 공약수를 쉽게 구할 수 있다.

 

증명 과정이 궁금하시다면 구글 검색하시고..

 

a 와  b 의 최대 공약수는 b 와 a % b 의 최대공약수 와 같다. 식으로 표현하면 gcd(a, b) = gcd(b, a % b) 이다.

그리고, gcd(n, 0) = n 이다.

 

예를들어, gcd(99, 15) = gcd(15, 9) = gcd(9, 6) = gcd(6, 3) = gcd(3, 0)

 

정리

• gcd(a, b) = gcd(b, a % b)
• gcd(n, 0) = n

위 2가지 성질을 이용해서 최대 공약수를 구해보자

 

Python 코드

아래 코드는 unittest 기반으로 작성되었다. 주요 로직은 euclid_gcd() 메소드를 참고한다.

# -*- coding: utf-8 -*-

import unittest


class Exam05(unittest.TestCase):
    """최대 공약수 구하기"""

...

    @classmethod
    def euclid_gcd(cls, a, b):
        if b == 0:
            return a  # gcd(n, 0) = n
        return cls.euclid_gcd(b, a % b)  # gcd(a, b) = gcd(b, a % b)

    def test_euclid_gcd(self):
        self.assertEqual(2, self.euclid_gcd(4, 6))
        self.assertEqual(14, self.euclid_gcd(14, 98))
        self.assertEqual(14, self.euclid_gcd(98, 14))
        self.assertEqual(3, self.euclid_gcd(15, 99))
        self.assertEqual(3, self.euclid_gcd(99, 15))


if __name__ == "__main__":
    unittest.main()

a 와 b 의 크기는 상관없다. (14, 98  두 수가 있을때, a, b = 14, 98 이든 a, b = 98, 14 이던지 상관없이 유클리드 알고리즘이 적용된다는 뜻)

 

결론

단순히 반복문 돌리면서 1씩 감소 시키는 방법도 있지만, 유클리드 알고리즘을 이용하여 최대 공약수를 구하는것이 효율적이다.

 

Reference

• https://thebook.io/006935/part02/ch05/02-01/