유클리드 호제법(Euclidean algorithm) [C++]

1. 정의

2개의 자연수의 최대공약수¹를 구하는 알고리즘²

mod(%) 연산자³를 통해 최대공약수를 구할 수 있다.

2. 예시

</img>

1. a 와 b를 mod 연산한다.
2. mod 연산의 결과가 0이 아닐시, b를 기준으로 mod 결과를 다시 mod 연산한다.
3. mod 연산의 결과가 0일 때까지 반복한다.
4. mod 연산의 결과가 0일 떄, b 가 최대공약수가 된다.

3. 코드

int gcd(int a,int b){
    int c = a % b;
    while(c){
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

a × b = GCD(a, b)¹ × LCM(a, b)² 성질을 이용하여 최소공배수⁴도 구할 수 있다.

4. 관련 문제

• [BOJ] 최대공약수와 최소공배수

5. 용어 및 출처

1. GCD(Greatest Common Divisor) = 최대공약수 : 두 수의 공약수 중 가장 큰 하나 ↩ ↩²

2. 유클리드 호제법 ↩ ↩²

3. mod(%) 연산 : 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산 ↩

4. LCM(Least common multiple) = 최소공배수 : 두 수의 양의 공배수 중 가장 작은 수 하나 ↩