유클리드 호제법

 

 

 

 

유클리드 호제법

: 두 수의 최대공약수(GCD)를 구하기 위한 수학적 알고리즘

 

 

반복적으로 큰 수를 작은 수로 나누면서 나머지를 계산해, 나머지가 0이 될 때의 나누는 수를 GCD로 반환

 

 

 

 

유클리드 호제법의 원리

 

두 정수 A와 B의 최대공약수를 구하려고 할 때:

1. A%B 를 계산하여 나머지를 구한다.
2. A를 B로, B를 나머지로 바꾼다.
3. 나머지가 0이 될 때까지 이 과정을 반복한다.
4. 나머지가 0이 되면, 그때의 B 값이 GCD가 된다.

 

 

 

유클리드 호제법 구현 (Java 코드)

class GCDExample {
    public static int getGCD(int a, int b) {
        // 유클리드 호제법
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a; // GCD 반환
    }
}

 

 

 

 

 

 

---

 

 

 

유클리드 호제법을 어디서 쓸까? 

 ex) 기약분수를 나타낼 때 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120808#

프로그래머스