📚 최대공약수(GCD)란?

두 수를 동시에 나눌 수 있는 가장 큰 수

---

📃 ex) 56와 24의 최대공약수

• 56의 약수 : 1, 2, 4, 7, 8, 14, 28, 56
• 24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24

두 수의 약수 중 공통된 약수는 1, 2, 4, 8
그 중 가장 큰 값인 8이 최대공약수 이다.

---

자 이제 코드로 구현을 한다고 생각해보자

간단하게 생각하면

1. for문을 돌려서 1부터 n까지 나누어 나머지가 0인 약수들의 집합을 만든다.
2. 두 수의 공통된 약수들을 구한다.
3. 그 중 가장 큰 값을 구한다.

복잡한 과정을 거처야하며 코드가 길어질 것이다.

그러나 더 쉬운 방법이 있다.

---

💡 유클리드 호제법

GCD(a, b) = GCD(b, a % b)
GCD(a, 0) = a

유클리드 호제법의 핵심은

두 수의 최대공약수는 작은 수와 큰 수를 나눈 나머지의 최대공약수와 같다

이 과정을 반복해서 나머지가 0이 될 때까지 수행하면,

마지막에 남은 작은 수가 두 수의 최대공약수이다.

---

📃 ex) gcd(56, 24)

• gcd(56, 24) = gcd(24, 56%24) = gcd(24, 8) = gcd(8, 24%8) = gcd(8, 0)

따라서 최대공약수는 8이다.

---

이를 코드로 변환하면

• 반복문

  def gcd(n, m):
      while m != 0:
          n, m = m, n % m
      return n

• 재귀

  def gcd(n, m):
      if m == 0
          return n
      else:
          return gcd(m, n % m)

---

📚 최소공배수(LCM)란?

두 수의 공통된 배수 중에서 가장 작은 수

최소공배수(LCM)은 최대공약수(GCD)로 구할 수 있다.

LCM(a, b) = a * b // GCD(a, b)

이는 두 수의 곱에서 공통된 약수를 제거하여 최소공배수를 구하는 방법이다.

이를 코드로 나타내면

def lcm(n, m):
	return n * m // gcd(n, m)