C# 유클리드 호제법 -재귀함수로 최대공약수 구하기

유클리드 호제법

 

두 양의 정수 a,b (a>b)에 대하여 a=bq+r (0≤r<b)이라 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉,

gcd⁡(a, b)=gcd⁡(b, r)

r=0이라면, a,b의 최대공약수는 b가 된다.

 

//코드
public int getgcd(int n, int m)
{
	if(m==0) return n;
    else return getgcd(m, n%m);
}
//숏코드
public int f(int n,int m) return m==0?n:f(m,n%m);