最大公约的两种求法：
代码如下：
#include<stdio.h>
int gcds(int a,int b)//stein算法
{
if(a<b){
int temp = a;
a = b;
b=temp;
}
if(0==b) //b=0返回
return a;
if(a%2==0 && b%2 ==0) //a和b都是偶数
return 2*gcds(a/2,b/2);
if ( a%2 == 0) // a是偶数，b是奇数
return gcds(a/2,b);
if ( b%2==0 ) // a是奇数，b是偶数
return gcds(a,b/2);
return gcds((a+b)/2,(a-b)/2);// a和b都是奇数
}
int gcdo(int a,int b) //欧几里得
{
if(b==0)
return a;
if(a<b){
int temp = a;
a = b;
b=temp;
}
return gcdo(b,a%b);
}
int main()
{
int a,b;
while(scanf("%d %d",&a,&b)!=EOF)
{
printf("%d\n%d\n",gcds(a,b),gcdo(a,b));
}
return 0;
} 欧几里得算法，当初老师给我们的时候，只是说这样求可以求得最大公约数，没给出证明。。
百度上搜了一下，基本证明思想a，b(a>b)的公约数和a，a%b的公约数是相同的。Stein算法证明也类似！！
posted on 2010-09-07 12:09
jince 阅读(759)
评论(0) 编辑 收藏 引用