[Python/파이썬] 프로그래머스 N개의 최소공배수

프로그래머스

 

코드

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

def solution(arr):
    lcm = arr[0]
    for i in range(1, len(arr)):
        lcm = lcm * arr[i] // gcd(lcm, arr[i])
    return lcm

최소공배수, 최대공약수 구할 때는 유클리드 호제법을 사용한다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법은 최대공약수를 구할 수 있는 알고리즘인데 간단히 설명해보자면 어떤 수 a, b의 최소공배수를 구하고자 할 때, a와 b를 나눈 나머지 r이라 할 때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이것을 이용하여 gcd라는 함수를 만들고 첫번째 인자를 두번째 인자로 나눈 나머지가 0이 될 때까지 재귀적으로 반복하여  a와 b의 최대공약수를 구할 수 있다.

최소공배수는 두 수의 곱을 최대공약수로 나누면 된다.