十八.欧几里得算法

欧几里得算法

unsigned int Gcd(unsigned int M,unsigned int N)
{
unsigned int Rem;
while(N > 0)
{
    Rem = M % N;
    M = N;
    N = Rem;
}
    return M;
}

此算法用来计算最大公因子。
两个整数的最大公因数（Gcd）是同时整除二者的最大整数。
例 : Gcd(50,15) = 5.
此算法先假设M>=N。(如果N>M，则循环的第一次迭代将它们互相交换)
算法连续计算余数直到余数是0为止，最后的非零余数就是最大公因数。因此，如果 M = 1989 和 N = 1590,则余数序列是399, 393, 6，3,0，。从而例子所表明的，这是一个快速算法。

完整代码：

#include<stdio.h>
unsigned int Gcd(unsigned int M,unsigned int N)
{
unsigned int Rem;
while(N > 0)
{
    Rem = M % N;
    M = N;
    N = Rem;
}
    return M;
} 
int main()
{   int M , N;
    Gcd(M,N); 
	scanf("%d %d",&M,&N);
	printf("%d",Gcd(M,N));
	return 0;	
}