[프로그래머스] [Level 2] N개의 최소공배수

문제) N개의 최소공배수

코딩테스트 연습 - N개의 최소공배수

 

• 내 풀이
  • 원소의 모든 값이 서로소일 경우를 고려해야 함

def solution(arr):
    arr.sort(reverse=True)
    answer=arr[0]
    for a in arr:
        if a==arr[0]:
            continue
        for i in range(1,a+1):
            if (answer*i)%a==0:
                answer=answer*i
                break
    return answer

arr1=[3, 4, 9, 16]
arr2=[3, 7, 11, 17, 19, 23, 29, 31, 37 #모든원소가 서로소일 경우
print(solution(arr1))
print(solution(arr2))
#결과
144
57082601037

 

• 다른 사람 풀이
  • 유클리드 호제법 사용해서 하나씩 비교

[Python] 파이썬- 최대공약수, 최소공배수

def solution(arr):
    answer = arr[0]
    for i in range(len(arr)-1) :
        answer = lcm(answer,arr[i+1])

    return answer

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

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