유클리드 호제법(Euclidean algorithm)

유클리드 호제법이란?

유클리드 호제법(Euclidean algorithm)은 유클리드 알고리즘이라고도 불리우며,

두 양의 정수 혹은 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘이다.

그리스 수학자 유클리드((Euclid)가 작성한 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라고 한다.

 

 

 

원리

GCD(a,b)=GCD(b,amodb)

 

두 수 a와 b (a>b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

이 과정을 반복하여 나머지가0이 될 때 나누는 수가 두 수의 최대공약수이다. 

 

1. 큰 수인 a를 b로 나눈 나머지 r을 구한다.
2. a를 b로 대체하고, b를 r로 대체한다.
3. 나머지 r이 0이 될 때까지 반복한다.
4. 나머지가 0이 되었을 때, 나누는 수가 최대공약수이다.

 

 

예제 풀이

56 / 42 -> 나머지는 14 (즉, 56 mod 42 = 14)
42 / 14 -> 나머지는 0 (42 mod 14 = 0)

최대공약수는 14.

 

 

 

예제 코드 #1 (java)

public class EuclideanAlgorithm {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(gcd(56, 42));  // 출력: 14
    }
}

 

 

 

예제 코드 #2 (python)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 사용 예시
print(gcd(56, 42))  # 출력: 14