Programmers - N개의 최소공배수

문제 링크

최대공약수 및 최소공배수 문제

최대공약수(GCD: Greatest Common Divisor)

유클리드 호제법

1. 두 자연수 A, B (A>B)
2. A%B = N 에서, N이 0일 때 B가 최대공약수
3. N이 0이 아니면 A->B , B->N 으로 변경 후 N이 0이 될 때 까지 반복

최소공배수(GCM: Greatest Common Multiple)

두 자연수 A,B 의 최소공배수 : (A*B)/gcd(A,B)

def solution(arr):
    def gcd(a, b):
        if a < b:
            return gcd(b, a)
        n = a % b
        if n == 0:
            return b
        else:
            return gcd(b, n)

    def gcm(a, b):
        return (a*b)//gcd(a, b)

    answer = arr[0]
    for num in arr:
        answer = gcm(answer, num)

    return answer