[이론] 유클리드 호제법

 🤔 유클리드 호제법이란?

"쉽고 빠르게 최대공약수를 구하는 방법"

 

두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 알고리즘이다. 이 글에서는 두 양의 정수의 최대공약수를 구하는 방법에 대해서만 서술할 예정이다.

 

최대공약수(GCD)는 두 수가 함께 나눌 수 있는 공약수 중 가장 큰 수를 말한다.
알고리즘을 구현할 때 유클리드 호제법(Euclidean Algorithm)을 사용하면 빠르고 간단하게 구할 수 있다.

---

 📌 원리

유클리드 호제법은 다음과 같은 수학적 원리를 기반으로 한다.

• 두 수 a, b (단, a > b)에 대하여 a = bq + r (0<=r<b)이라 하면,
• a와 b의 최대공약수는 b와 r의 최대공약수와 같다.*
  즉, GCD(a, b) = GCD(b, r) = GCD(a, a%b)

이 과정을 나머지가 0이 될 때까지 반복하면,
0이 되기 직전의 수가 최대공약수이다.

---

 ✅ 예시

🔹 30과 45의 최대공약수

1. 45 ÷ 30 = 1 ... 15
2. 30 ÷ 15 = 2 ... 0
   → 최대공약수는 15

---

 ⌨️ C언어 구현 코드

유클리드 호제법을 C언어로 구현할 때는 재귀함수를 이용한다.

int gcd(int n, int m) {
    if (n < m) swap(n, m);
    if (m == 0) return n;
    else
        return gcd(m, n % m);
}

---

 ✍🏻관련 문제

2609번: 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609

 

문제풀이
[BOJ C++] 백준 2609번: 최대공약수와 최소공배수