[자료구조] 수학 - 최대 공약수 & 최소 공배수 with Python

🔷 최대 공약수란?

GCD (Greatest Common Divisor)

→ 두 수 혹은 그 이상의 여러 수의 약수 중 공통이며 가장 큰 수

• 8의 약수 - 1, 2, 4, 8
• 10의 약수 - 1, 2, 5, 10
• 8과 10의 공통 약수 - 1, 2 중 가장 큰 수 : 2
• 8과 10의 최대공약수 - 2

🔶 최소 공배수란?

LCM ( Least Common Multiple)

→ 두 수 혹은 그 이상의 여러 수의 배수 중 공통이며 가장 작은 수

• 10의 배수: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, …
• 12의 배수: 12, 24, 36, 48, 60, 72, 84, 96, 108, 120, …
• 10과 12의 공통 배수 - 60, 120, …
• 10과 12의 최소 공배수 : 60

🟢 최대 공약수 & 최소 공배수 구현하기

• for문을 통해서 구하기

a = 10
b = 20

# 최대 공약수 구하기
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 i % a == 0 and i % b == 0:
				print(i)
				break

• 최대 공약수:
  • a, b 중 작은 숫자부터 1까지 -1을 하며 for문을 실행
  • a%i와 b%i를 하였을 때 모두 값이 딱 떨어져서 나머지가 없는 상태라면 i는 a와 b의 최대 공약수

→ 공통 약수들 중에서 가장 큰 수를 구하는 것이므로 for문을 주어진 수부터 1까지 -1을 하며 실행

• 최소 공배수:

  • a, b 중 큰 숫자부터 a*b의 수 까지 for문을 실행

    ✔️ 큰 숫자부터 실행하는 이유는 a, b의 배수들 중 공통 부분을 찾는 것이기 때문에 a, b 중 작은 수부터 시작하게 되면 i가 i++이 되면서 둘 중 큰 수에 도달할 때 까지 for문은 헛돌게 된다.

  • i%a 와 i%b 모두 값이 떨어져서 나머지가 없는 상태라면 이 때 사용된 i는 a와 b의 최소 공배수

→ 공통 배수들 중에서 가장 작은 수를 구하는 것이므로 for문을 주어진 수부터 +1을 하며 실행

어디부터 시작하는 건 상관없지만 최대한 빨리 찾아서 for문을 끝내는게 시간, 자원적으로 효율이 좋기 때문이다.

🟢 유클리드 호제법

유클리드 호제법이란?

x, y의 최대공약수는 y, r의 최대공약수와 같다는 원리를 이용
x와 y의 최대공약수 == y와 r의 최대공약수
→ 계속해서 x에는 y값을 대입하고 y에는 (x&y)값인 r을 대입하다보면 x%y == 0을 찾을 수 있다.

🟢 유클리드 호제법 구현

# 최대공약수 구하기
def GCD(x, y):
		while(y):
				x, y = y, x%y
		return x
print(GCD(10, 12))

# 최소공배수 구하기
def LCM(x, y):
		result = (x*y)//GCD(x, y)
			return result
print(LCM(10, 12))

🟢 math 라이브러리 활용하여 구현하기

import math
# 최대 공약수
def gcd(x, y):
		return gcd(x, y)

# 최소 공배수
def lcm(x, y):
		return lcm(x, y)