[Algorithm/문해기] 유클리드 호제법_최대공약수

 최대 공약수 : Greatest Common Divisor, GCD

 

for 문을 이용해 min(m,n) 번의 if 문을 시행하려 든다면 두 변수의 크기가 커질수록 많은 시간 자원을 이용하게 된다. 따라서 유클리드 호제법을 이용한다. 

 

유클리드 호제법 정리. 두 정수 m,n의 최대 공약수를 구하기 위해서는 이보다 크기가 작은 m(m<=n)과 r의 최대 공약수를 구하는 것이다.  

여기서 r = n - mq 이다. (따라서 m>=r) 이때 두 수 중 하나가 0이 되는 순간, 나머지 하나가 최대 공약수가 된다. 

 

 

gcd(m,n) = gcd(m,r) 

 

 

 

<소스 코드>

#include <iostream>

using namespace std;

int n,m;

int gcd(int m, int n){

    if(m==0) return n;

    else return gcd(n%m,m);

}

int main()

{

    cin>>n>>m;

    cout<<gcd(n,m)<<"\n";

}