[Algorithm] 최대공약수 GCD (유클리드 호제법)

호제법

• 두 수가 서로 상대방 수를 나눠서 결국 원하는 수를 얻는 알고리즘

 

두 수 A, B의 최대공약수를 G라고 하면

1. A = Ga / B = Gb → A를 B로 나누면 (A≥B라고 가정)
2. A = BQ + R → Q : 몫, R : 나머지
3. Ga = GbQ + R
4. R = G(a-bQ) ≫ G는 A를 B로 나눈 나머지의 약수 

---

Example

A : 20 / B : 55 → GCD(A, B)

1. 20%55 = 20 → GCD(55, 20)
2. 55%20 = 15 → GCD(20, 15)
3. 20%15 = 5 → GCD(15, 5)
4. 15%5 = 0 → GCD(5, 0) → B가 0이 되는 순간 알고리즘 종료 → 최종 최대공약수 = A

 

Java Code

static int GCD(int A, int B){
        if(B==0) return A;
        else return GCD(B, A%B);
    }

---

최소공배수 : (A*B)/GCD(A, B)