[Python] N개의 수의 최대 공약수, 최소 공배수 구하기

최대공약수

먼저 두 수의 최대공약수를 구하는 알고리즘은 다음과 같다.

def gcd_(a, b):
    while b>0:
      a,b=b,a%b
    return a

arr[0]~arr[N-1] N개의 수가 주어졌을 때 최대 공약수를 구해보자
arr[0]과 arr[1]의 최대공약수 gcd라고 하면, gcd를 gcd와 arr[2]와의 최대공약수로 갱신해주고, 다시 gcd와 arr[3]의 최대공약수를 구하는 것을 반복 해 주면 된다.

def gcd_N(arr):
      gcd=arr[0]
      for item in arr:
        gcd=gcd_(gcd,item)
      return gcd

 

 

 

 

최소공배수

먼저 두 수의 최소공배수를 구하는 알고리즘은 다음과 같다.

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

arr[0]~arr[N-1] N개의 수가 주어졌을 때 최소공배수를 구해보자
arr[0]과 arr[1]의 최소공배수 lcm라고 하면, lcm를 lcm와 arr[2]와의 최소공배수로 갱신해주고, 다시 lcm와 arr[3]의 최소공배수를 구하는 것을 반복 해 주면 된다.

def lcm_N(arr):
    lcm=1
    for item in arr:
        lcm=lcm_(lcm,item)
    return lcm