[알고리즘] 최소공배수, 최대공약수

최대 공약수 GCD ( Greatest Common Divisor)

수 들의 각각의 약수중 공통이며 가장 큰 수를 최대 공약수라고 한다.

최소 공배수 LCM ( Least Common Multiple)

수 들의 각각의 배수 중 공통이며 가장 작은 수를 최소 공배수라고 한다.

---

• 일반 for문으로 구하기
  

  a = 10
  b = 12
    
    # 최대공약수
    for i in range(min(a,b),0,-1):
    	if a % i == 0 and b % i ==0:
    		print(i)
    		break
    
    # 최소 공배수
    for i in range(max(a,b),(a*b)+1):
    		if a % i == 0 and b % i ==0:
    		print(i)
    		break

• 유클리드 호제법을 사용하기
  • x % y = r (x를 y로 나눈 나머지값 == 0)
  • x,y의 최대공약수는 y,r의 최대 공약수와 같다.

예시

a = 10
b = 12

# x % y == r
10 % 12 == 10

12 % 10 == 2

10 % 2 == 0

# 나머지 값이 0일때의 y값이 최대 공약수

• 유클리드 호제법을 이용한 파이썬 알고리즘

# 최대 공약수
def GCD(x,y):
	# y가 참일동안 == 자연수일 때 == a % b != 0
	while(y)
		x,y = y, x%y
	return x

# 최소 공배수
def LCM(x,y):
	result = (x*y) // GCD(x,y)

• math 함수를 이용해서 풀 수도 있다.

import math

# 최대공약수
print(math.gcd(a,b))
# 최소 공배수
print(math.lcm(a,b))