[C++] 유클리드 호제법 (최대공약수, 최소공배수)

 

유클리드 호제법 또는 유클리드 알고리즘

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

 

예시) 1112와 695를 반복해서 MOD 연산

유클르드 호제법

유클리드 호제법(Euclidean-algorithm)

 

 

• 최대공약수 GCD (Greatest Common Divisor)
  • 139일 때 나머지가 0이 되므로 최대공약수는 139가 된다.
• 최소공배수 LCM (Least Common Multiple)
  • 두개의 수를 곱한 뒤 최대공약수로 나눠주면됨
  • (1112 * 695) / 139 = 5560

 

코드

// 반복문
int GCD_Func_(int a, int b) {
    int tmp;
    do {
        tmp = a % b;
        a = b;
        b = tmp;
    } while(tmp);
    
    return a;
}
 
// 재귀
int GCD_Func_(int a, int b) {
    int tmp = a % b;
    if(tmp == 0) {
        return b;
    } else {
        return GCD_Func_(b, tmp);
    }
}