알고리즘 수학

유클리드 호제법으로 최대공약수(GCD) 구현방법

이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될 때까지 작동하여 최대공약수를 구하는 방식입니다.
두 수 중에 큰 수를 a에 넣고 재귀적으로 반복하여 b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대공약수를 구합니다.

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}