유클리드 호제법

유클리드 호제법은 두 자연수의 최대공약수(Greatest Common Divisor, GCD)를 찾는 알고리즘임

큰 수에 대해서도 빠르게 최대공약수를 계산이 가능

 

두 자연수 A와 B가 있을 때 (A>B), A를 B로 나눈 나머지를 R이라고 합시다.

이때, A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.

이 성질을 반복적으로 사용하여 나머지가 0이 될 때까지 과정을 반복합니다.

나머지가 0이 되는 단계에서의 나누는 수가 A와 B의 최대공약수입니다.

예시

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int A = 252, B = 105;
    cout << "GCD of " << A << " and " << B << " is " << gcd(A, B) << endl;
    return 0;
}