高考问答长春郝树春手下:求两个最大公约数的算法
来源：百度文库 编辑：高考问答 时间：2024/05/08 14:51:04
利用辗转相除法可以解决:
求a,b的最大公约数:(a,b)
a=bq1+r1;
b=r1q2+r2;
...
rn-1=rnqn+1;
那么(a,b)-rn.有关证明请看有关数论中数的整除性文章.
下面用C的伪代码说明算法.
可定义变量,a,b,r,c;
if(a<b) {利用c把a,b交换}
if(!a%b) cout << "(a,b)=" <<b;
else {
r=a%b;
a=b;
b=r;
}
a为第一个数，b为第二个数
int min=Min(a,b)//求出最小的那个数
for(i=1;i<=min;i++)
{
if(a%i==0&&b%i==0)
maxconven=i;//当a除以这个数余数为0和b除以这个数余数为0则这个数就是a,b的公约数
}
cout<<maxconvert