Dev Uni

유클리드 호제법

3 min read

최대공약수를 구하는 방법. 두 수를 소인수분해할 필요 없이 나머지 연산만 반복하면 나온다.

나머지로 줄여가는 원리

원리는 한 줄이다. A를 B로 나눈 나머지를 R이라고 하면 GCD(A, B) = GCD(B, R)이다.

나머지가 0이 되면 그때의 B가 최대공약수다. 나머지가 0이 아니면 A 자리에 B를, B 자리에 R을 넣고 다시 반복한다. 숫자가 매번 확 줄어드니 몇 번 만에 끝난다. 전제는 A가 B보다 크다는 것인데, 작아도 첫 번째 나눗셈에서 자동으로 자리가 바뀌므로 신경 쓰지 않아도 된다.

재귀가 원리를 그대로 옮긴 모양이다.

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

반복문으로도 똑같다.

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

최소공배수

최소공배수는 덤이다. 두 수 A, B의 최대공약수를 G, 최소공배수를 L이라고 하면 A × B = L × G가 성립한다. 그래서 최대공약수만 구하면 최소공배수는 나눗셈 한 번이다.

int lcm = a * b / gcd(a, b);

a * b가 int 범위를 넘을 수 있으니 큰 수를 다룰 때는 a / gcd * b 순서로 계산하거나 long을 쓴다. 오버플로우가 나는 대표적인 자리다.

관련

출처