[Python] 최대공약수 & 최소공배수 구하기

1. 최대 공약수

- 기본 알고리즘

# 두 수의 최대 공약수 구하기
def gcd(a,b):
	while b > 0:
    	a,b = b, a%b
    return a

 

 

- 모듈 이용

from math import gcd
g = gcd(a, b)

 

 

 

- 응용 (array내 숫자의 최대 공약수 구하기)

def gcd_n(arr):
    gcd = arr[0]
    for i in arr:
        gcd = math.gcd(gcd, i)
    return gcd

 

 

 

 

 

2. 최소 공배수

- 기본 알고리즘

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

 

 

 

- 모듈 이용

from math import lcm
l = lcm(a,b)

 

 

 

 

- 응용 (array내 숫자의 최소 공배수)

def lcm(arr):
	lcm = 1
    for i in arr:
    	lcm = math.lcm(lcm, i)
    return lcm