유클리드 호제법, 최대 공약수 알고리즘

점화식

유클리드 호제법을 통해 수 A, B의 최대 공약수를 구하는 과정은 다음과 같다.

A > B일 때, (Q0는 몫, R0는 나머지)

A = Q0 * B + R0

B = Q1 * R0 + R1

R0 = Q2 * R1 + R2

...

Rn = Q(n+2) * R(n+1) + R(n+2) 일 때, R(n+2)가 0 이라면, A와 B의 최대공약수는 R(n+1)이다.

 

알고리즘(C++)

#include <iostream>
using namespace std;

int euclid(int  A, int B){
 if(A%B == 0) return B;
 else return euclid(B, A%B);
}

int main(){
 cout<< "수 2개 입력 >>";
 int A,B;
 cin>>A;
 cin>>B;
 
 if(A<B){ //큰 수를 A로 두기 위해 swap
  int temp = A;
  A = B;
  B = temp;
 }
 
 cout<<"최대 공약수: "<<euclid(A, B)<<endl;
 return 0;
}