[Python] 최소공배수(LCM) 구하기

 

Python을 사용해 최소공배수를 구해보겠습니다.

 

### 최소공배수 ?

 

위키피디아 정의

수론에서, 여러 개의 정수/다항식/환의 원소의 
공배수(common multiple)는 그들 모두의 배수가 되는 정수/다항식/환의 원소이다. 
최소공배수(least/lowest common multiple, LCM)는 양의 공배수 가운데 가장 작은 하나이다. 
유클리드 정역에서 0으로 나누기를 정의하지 않으므로, 
이 정의는 오직 다루고자 하는 정수들이 0이 아닐 때 의미가 있다. 

출처 : https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

 

common multiple : 공통 배수

least commun multiple : 최소 공통 배수

 

즉, 공통된 배수들 중 가장 작은 수 입니다.

 

 

## Python 최소공배수 구하기

 

1. 소인수 분해

 

두 수를 소인수 분해 합니다.

각 소인수 중 지수가 가장 큰 수를 곱합니다.

지난 시간에 포스팅한 소인수 분해 함수를 사용하겠습니다.

 

 

2021/01/02 - [알고리즘] - [Python] 소인수 분해하기

[Python] 소인수 분해하기

 

제가 구현한 최종 코드는 다음과 같습니다.

 

def get_prime_factor(num):
    from collections import defaultdict
    dic=defaultdict(int)
    
    d=2
    
    while d<=num:
        if num%d==0:
            dic[d]+=1
            num=num/d
        else:
            d+=1
        
    return dic

dic1=get_prime_factor(12)
dic2=get_prime_factor(15)

keys=list(set(list(dic1.keys())+list(dic2.keys())))

res=1
for i in keys:
    res=res * pow(i,max(dic1[i],dic2[i]))
print(res)

 

소인수 분해 함수에 추가된 내용

 

두 딕셔너리의 키를 중복 제거해서 리스트로 저장(keys 리스트)

키를 사용해 두 딕셔너리 중 값이 큰 값을 선택(max(dic1[i], dic2[i]) )

 

결과를 출력할 res x 키 ^ 값 으로 누적 저장합니다.

 

조금 더 나은 방법이 있을 것 같아요 .

공부 해 보겠습니다.

2. 1 ~ 두 수의 곱까지 나누셈 진행

def get_prime_factor(num1,num2):
    for i in range(1,num1*num2):
        if i%num1==0 and i%num2==0:
            return i
        
get_prime_factor(12,15)

 

i는 1부터 점차 증가합니다.

1,2,3, .... 12*15

i를 12와 15로 나누어 둘 다 나머지가 0이 된 순간

그 i는 최소 공배수가 됩니다.

간단한 코드이지만 큰 수의 경우 오래걸릴 수 있고

비 효율적인 코드입니다.

 

3. 공식 이용

 

LCM = n1 * n2 / GCD

 

최대 공약수를 구하는 방법은 이미 코드로 구현을 해보았습니다.

이를 이용해 아주 간단하게 최소공배수를 구할 수 있게 되었습니다.

 

2020/12/31 - [알고리즘] - [Python & SQL ] 최대 공약수 구하기

[Python & SQL ] 최대 공약수 구하기

num1=int(input('첫 번째 숫자를 입력하세요 : '))
num2=int(input('두 번째 숫자를 입력하세요 : '))

def get_GCD(num1,num2):
    while num1%num2!=0:
        (num1,num2)=(num2,num1%num2)
    return num2
        
if max(num1,num2)%min(num1,num2)==0:
    gcd=min(num1,num2)
else:
    gcd=get_GCD(num1,num2)
    
lcm=num1*num2/gcd

print('%d,%d 최소공배수 : %d'%(num1,num2,lcm))

 

아주 쉽게 결과를 확인할 수 있습니다.

 

 

### 세 가지 방법 소요 시간 비교

 

datetime 모듈을 사용

걸린 시간 : 코드 시작 시간 - 코드 마지막 print 출력 시간

여러가지 방법에 걸린 시간을 비교해 보았습니다.

 

 

1. 소인수 분해 함수 이용

 

2. 두 수의 곱 범위까지 나누기

 

 

 

3. 유클리드 호제법 & 최대공약수로 나누기

 

 

 

 

유클리드 호제법을 사용해 최대 공약수를 찾고,

두 수의 곱을 최대 공약수로 나누는 방법이 가장 빨랐습니다.

 

반면에 1부터 두 수의 곱까지 나누어 나가는 방법은 약 3분 11초가 소요되었습니다.

 

읽어주셔서 감사합니다