유클리드 호제법(Euclidean algorithm)

유클리드 호제법(Euclidean algorithm)은 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘 중 하나이다. 이 알고리즘은 고대 그리스의 수학자 유클리드(Euclid)에 의해 고안되었으며, 두 정수의 최대공약수를 효과적으로 찾는 데 사용된다.

최대공약수(Greatest Common Divisor, GCD)는 두 개 이상의 정수의 가장 큰 공약수를 나타내는 개념이다. 공약수는 주어진 두 수의 모두에 나누어 떨어지는 수를 말하며, 최대공약수는 이러한 공약수 중에서 가장 큰 수를 의미한다.
 두 수 24와 36의 경우 공통된 약수는 1, 2, 3, 4, 6, 12이다. 이 중에서 가장 큰 수인 12가 두 수 24와 36의 최대공약수가 된다. 따라서 GCD(24, 36) = 12입니다.

 

 

유클리드 호제법의 기본 원리

---

1. 두 정수 a와 b에 대해 a > b 라면 a를 b로 나눈다.
2. 나머지를 r이라고 한다.
3. 나머지 r이 0이 아니라면, r을 b로 다시 나눈다.
4. 나머지가 0이 될 때까지 반복한다. 이때, 나누는 수가 최대공약수가 된다

public int gcd(int x, int y){
	if(y == 0)
    	return x;
    else
    	return gcd(y,x % y);
}

public int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
}