甜橘子，专注成都网站制作网站设计与营销型网站建设与优化
QQ :532337155
电话：028-86922220
辗转相除法用来求两个数的最大公约数，代码如下：
站在用户的角度思考问题，与客户深入沟通，找到南召网站设计与南召网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：成都做网站、网站制作、成都外贸网站建设、企业官网、英文网站、手机端网站、网站推广、空间域名、网络空间、企业邮箱。业务覆盖南召地区。
#include stdio.h
#include stdlib.h
int main()
{
int a, b,r;
scanf("%d %d", a, b);
while(b!=0)//当其中一个数为0，另一个数就是两数的最大公约数
{
r = a%b;
a = b;
b = r;
}
printf("Greatest Common Divisor: %d\n", a);
system("pause");
}
运行结果：
用辗转相除法（即欧几里得算法）求两个正整数的最大公约数。
解析：
设两个数m,n，假设m=n，用m除以n，求得余数q。若q为0，则m为最大公约数；若q不等于0，则进行如下迭代：
m=n,n=q,即原除数变为新的被除数，原余数变为新的除数重复算法，直到余数为0为止。余数为0时的除数n，即为原始m、n的最大公约数。
迭代初值：m，n的原始值；
迭代过程：q=m%n;
m=n;
n=q;
迭代条件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因为：(q==2)!=0，重复算法：
q=m%n(6%2==0)
m=n(m==2)余数为0时的除数n为最大公约数，n值赋给了m，所以输出m的值
n=q(n==0)
因为：q==0 所以最大公约数为m的值
源程序：
#includestdio.h
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",a,b);
m=a;
n=b;
if(nm)
{
int z;
z=m;m=n;n=z;//执行算法前保证m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %d\n",a,b,m);
}
希望对你有所帮助!
例如用辗转相除法求a b 最大公约数（a b谁大谁小无所谓）：
int GCD( int a , int b )
{
int n=a%b;
whie(n != 0) //即： while(n)
{
a = b;
b = n;
n = a % b;
}
return b; //注意这里返回的是b 不是n
}
用辗转相除法（即欧几里得算法）求两个正整数的最大公约数.
解析：
设两个数m,n,假设m=n,用m除以n,求得余数q.若q为0,则m为最大公约数；若q不等于0,则进行如下迭代：
m=n,n=q,即原除数变为新的被除数,原余数变为新的除数重复算法,直到余数为0为止.余数为0时的除数n,即为原始m、n的最大公约数.
迭代初值：m,n的原始值；
q=m%n;
m=n;
n=q;
迭代条件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因为：(q==2)!=0,重复算法：
q=m%n(6%2==0)
m=n(m==2)余数为0时的除数n为最大公约数,n值赋给了m,所以输出m的值
n=q(n==0)
因为：q==0 所以最大公约数为m的值
源程序：
#include
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",a,b);
m=a;
n=b;
if(nm)
{
int z;
z=m;m=n;n=z;//执行算法前保证m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %d\n",a,b,m);
}
希望对你有所帮助!
#include stdio.h
/*辗转相除法函数*/
int gcd_div(int a,int b)
{
if (b == 0) {
return a;
} else {
return gcd_div(b,a % b);
}
}
/*更相减损法函数*/
int gcd_sub(int a,int b)
{
int ma,mb;
ab?(ma=a,mb=b):(ma=b,mb=a);
if (mb == 0) {
return ma;
} else {
return gcd_sub(ma-mb,mb);
}
}
int main()
{
int a = 28,b = 21;
printf("最大公约数(减法):(%d %d)%d\n",b,a,gcd_sub(b,a));
printf("最大公约数(除法):(%d %d)%d\n",b,a,gcd_div(a,b));
return 0;
}