0%

최소공배수와 최대공약수

작성일 In Disqus:

파이썬으로 최대공약수, 최소공배수 구하기

최대공약수

최대공약수란?

최대공약수는 0이 아닌 정수들 사이의 공약수 중 가장 큰 공약수를 말한다.

구현

단순한 계산식 이용

  • 0이 아닌 두 정수 M, N 이 있다면, 1부터 둘 중 작은 수까지 나누어 보고, 나눠지는 수 중 가장 큰 수가 최대공약수일 것이다.
1
2
3
4
5
6
7
N, M = 100, 450

for num in range(1, min(N, M) +1):
    if N % num == 0 and M % num == 0:
        GCD = num
print(GCD)
>>> 50

위의 풀이로 계산을 한다면, 시간 복잡도는 O(N)이다.

유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

정의

2개의 자연수 a, b (a > b)에 대해 a를 b로 나눈 나머지가 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

GCD(a,b) = GCD(b, a % b), (r > 0)일 때 

1
2
3
4
5
6
7
8
9
10
11
12
13
# 반복문 이용
def GCD(a, b):
    while b > 0:
        a, b = b, b % a
    return a

# 재귀 이용
def GCD(a, b):
    r = b % a
    if r == 0:
        return a
    else:
        return GCD(b, r)

최소공배수

최소공배수는 최대공약수를 이용하여 구할 수 있다.

lcm(a,b) = a*b/gcd(a,b)

구현

위에서 구현한 gcd 함수를 이용하면 쉽게 구현할 수 있다.

1
2
def LCM(a, b):
    return a * b // GCD(a,b)