알고리즘 - 최소공배수

최소공배수

• 공배수 : 두 개 이상 자연수의 공통인 배수
• 최소공배수 : 공배수 중에서 가장 작은 수

ex) 36과 48의 최소공배수를 구해라
36 = 2 x 2 x 3 x 3
48 = 2 x 2 x 3 x 2 x 2

2 x 2 x 3은 두 수의 최대공약수이다.
36 = 최대공약수 x 3
48 = 최대공약수 x 4
최소공배수 = 최대공약수 x 3 x 4

36 x 48 = 최대공약수 x 최대공약수 x 3 x 4
-> 최소공배수 = 36 x 48 / 최대공약수

최소공배수 코드

def lcm(n1, n2):
    a,b = n1,n2
    if b > a: 
        a,b = b,a

    while b != 0:
        a = a % b
        a,b = b,a        # 최대공약수 구하기(a = 최대공약수)
        
    res = n1*n2 // a     # 최소공배수 구하기
    return res

문제 1

1부터 10까지의 최소공배수는 2520이다. 1부터 20까지의 최소공배수는 얼마인가?

def lcm(n1, n2):       # 최소공배수 구하는 함수
    a,b = n1,n2
    if b > a: 
        a,b = b,a

    while b != 0:
        a = a % b
        a,b = b,a
        
    res = n1*n2 // a
    return res
    
def lcmFromTo(start, end):     # 범위값의 최소공배수를 구하는 함수
    l = start
    for i in range(start+1, end+1):
        l = lcm(l, i)          # 루트를 통해 범위값을 주면서 l을 증가시켜 그 둘의 최소공배수를 구한다.
    
    return l
    
print(lcmFromTo(1, 20))
-> 232792560

문제 2

다음 리스트 원소들의 최소공배수를 구하시오.
[11, 13, 15, 16, 17, 19, 20, 25, 30]

def lcm(n1, n2):       # 최소공배수 구하는 함수
    a,b = n1,n2
    if b > a: 
        a,b = b,a

    while b != 0:
        a = a % b
        a,b = b,a
        
    res = n1*n2 // a
    return res
    
def lcmlist(n_list):     # 리스트값의 최소공배수를 구하는 함수
    for i in n_list[1:]:
        print(l, i)
        l = lcm(l, i)
    
    return l

print(lcmlist(n_list))

** 출처

• 주니온TV 아무거나연구소 - 코린아, 코딩하자 (with 파이썬)