以前用的都是穷举法~~
这次看书看到一个新方法,叫欧几里得算法~

long gcd( long m, long n ) //m>n
{
while( n!=0 )
{
long rem = m % n;
m = n;
n = rem;
}

return m;
}

有谁可以给出个严格的数学证明给我??

谢谢了~~

我晕，用穷举法都有的。。。
这个的证明很简单，就是gcd(m,n)=gcd(n,m%n)

另外还有一种算法，从效率上来看比欧几里得算法还要更高
int Gcd(int a, int b)
{
if(a == 0) return b;
if(b == 0) return a;
if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a >> 1, b >> 1);
else if(a % 2 == 0) return gcd(a >> 1, b);
else if(b % 2 == 0) return gcd(a, b >> 1);
else return gcd(abs(a - b), Min(a, b));
}

我想要数学证明啊~~为什么这个gcd 算法是可行的~~

证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.
Hint:
根据除法的定义不难证明:
1 如果d整除u和v, 那么d一定能整除u±v;
2 如果d整除u,那么d也能够整除u的任何整数倍ku.
对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r)

很好，都这样用，还真没想过原理！

纯原理....

谢了,我会认真去看的~~

我看不懂 老实话 主要我都不知道你哪个是要求的公约数
原理出来了更````