[Python] 최소공배수, 최대공약수 파이썬으로 구현하기(유클리드 호제법)

최대공약수

GCD(Greatest Common Divisor) : 두 수 혹은 그 이상의 수들의 공통인 약수 중 가장 최대인 수

10의 약수 - 1, 2, 5, 10
20의 약수 - 1, 2, 4, 5, 10, 20

10과 20의 최대 공약수 - 10

 

최소공배수

LCM(Least Common Multiple) : 두 수 혹은 그 이상의 수들의 공통인 배수 중 가장 최소인 수

10의 배수 - 10, 20, 30, 40, 50...
20의 배수 - 20, 40, 60, 80, 100...

10과 20의 최대공배수 - 20

 

For 문을 이용한 최대 공약수, 최소 공배수 구하기

 

최소공배수

for i in range(max(a, b), (a * b) + 1): #최소공배수
    if i % a == 0 and i % b == 0:
    	return i

i라는 값을 돌려줄 때, 최소공배수이므로 적어도 max(a,b) 보다는 커야 한다. 그리고 진짜 가장 크게 나올 수 있는 최소공배수는 a*b이다.

그러므로 max(a,b) 부터 a*b까지 i를 돌려가면서 최소공배수가 정말 없는지 찾아본다.

i를 a로도 나누어보고, b로도 나누어봐서 둘 다 0으로 떨어지면 두 수의 최소공배수가 맞다.

import math
math.lcm(a,b)

그렇지만 저렇게 코드를 짤 필요도 없이, 파이썬에서는 lcm이라는 라이브러리를 제공한다...

파이썬은 신이다.

 

최대공약수

for i in range(min(A,B), 0, -1):
	if A % i == 0 and B % i == 0:
    	print(i)
        break

최소공배수도 마찬가지로 for문을 돌려보면서 알 수 있다.

하지만 a와 b를 i로 나누어본다는 점이 다르다. 동시에 나누어지는 값이 최소공배수이다.

그리고 최대를 찾는 것이기 때문에 min(a,b)처럼 가장 크게 나누어떨어지는 값부터 시작해서, 1이 될때까지 나누어본다.

 

최대공약수, 유클리드 호제법

유클리드 호제법

def gcd(m,n):
	if m < n:
    	m, n = n, m #무조건 n이 더 작은 수(n이 중심임)
    if n == 0: #n이 0이 되면 m 반환해주기
    	return m
    else:
    	return gcd(n, m%n)

우선 무조건 m과 n의 크기를 비교해준 다음에, n이 더 작은 수가 되도록 설정해준다.

계속해서 함수에 n을 넣어줄 것이기 때문이다.

n이 0이 되면 m이 최대공약수가 되고(m%n = 0, n = m인 상태로 재귀에 들어갔기 때문), m%n이 0이 된다면 n이 최대공약수가 된다.

 

유클리드 호제법을 이용한 최소공배수

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