유클리드 호제법

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.

유클리드 알고리즘은 "2개의 자연수 a,b 에대해 a를 b로 나눈 나머지를 r 이라고 하면(a>b) a와 b의 최대공약수는 b와 의 최대공약수와 같다." 이다.
즉 저 말대로 구현해보자.

#include<iostream>
using namespace std;

int gcd(int a, int b){
    a=max(a,b);
    b=min(a,b);
    
    int r=a%b;
    
    if(r==0) return b;
    
    else return gcd(b,r);
}

예시 :
1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

출처 : 위키백과 :https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95