求最大公因数的证明~~
以前用的都是穷举法~~这次看书看到一个新方法,叫欧几里得算法~
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));
}
