欧几里得算法基本思想: Gcd(a,b) = Gcd(b , a%b)  直到最后余数为0

例如 Gcd(70,15) = Gcd(15,10)            70%15 = 10

Gcd(15,10) = Gcd(10,5)               15%10 = 5

Gcd(10,5)  = Gcd(5,0)                  10%5 = 0        余数为0 计算结束，最后结果为 5

这里还有一些比较有意思的定理       如果 M > N, 则 M mod N < M/2

有兴趣的可以自己证明一下  提示分为两种情形   1  N <= M/2     2  N > M/2

#include<stdio.h> //  欧几里得算法

//  用于求两个整数的最大公因数
int Gcd( int M,int N)
{
int Rem;
// 如果M < N  第一次运算将他们互换
while(N > 0) //当余数为0时循环终止
{
Rem = M % N;
M = N;
N = Rem;
}

return M;

}


int main(void)
{
printf("%d",Gcd(70,15));
return 0;
}