[Python] 최대공약수, 최소공배수 구하기

1. import math

math 라이브러리를 불러올 수 있다면 이게 제일 간단한 방법이다. 

 

import math

print(math.gcd(12, 32))
print(math.gcd(11, 33, 55))

print(math.lcm(7, 13))
print(math.lcm(6, 9, 12))

 

4
11
91
36

2. 유클리드 호제법

 

유클리드 호제법이란 두 정수 a와 b에서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 알고리즘이다. 

이를 코드로 나타내보면 아래와 같다.

 

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

def lcm(a, b):
    return int(a * b / gcd(a, b))


def gcdlcm(a, b):
    answer = [gcd(a,b), lcm(a,b)]

    return answer

 

 

3. 직접 구하기

말 그대로 하나하나 확인하는 방법. 시간 복잡도가 굉장히 비효율적이라 위의 두 방법을 추천한다.

def solution(n, m):
    # 최대 공약수
    for i in range(min(n, m), 0, -1):
        if (n % i == 0) and (m % i == 0):
            a = i
            break
    # 최소 공배수    
    for j in range(max(n, m), (n * m) + 1):
        if j % n == 0 and j % m == 0:
            b = j
            break
        
    return [a, b]