本文目录一览：
c语言辗转相除法求最大公约数
可用递归来求。
推荐以下代码：
#includestdio.h
int gcd(int a,int b) //求最大公约数函数
{
if (a%b==0) return b;
else return gcd(b,a%b); //辗转相除法
}
void main()
{
int a,b;
scanf("%d%d",a,b);
printf("%d\n",gcd(a,b));
}
c语言中，用辗转相除法计算两个数的最大公约数的具体方法是怎样的？
#include stdio.h
int gcd(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
int main(void) {
int a, b;
printf("Input two integers: \n");
scanf("%d%d", a, b);
printf("The greatest common divisor is: %d\n", gcd(a, b));
return 0;
}
原理：
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数，则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是：
1. a ÷ b，令r为所得余数（0≤rb）
若 r = 0，算法结束；b 即为答案。
2. 互换：置 a←b，b←r，并返回第一步
如何用C语言求两个数的最大公约数的三种算法
1、相减法
#includelt;stdio.hgt;
int main()
{
int a,b;
int c=0;//计数器
while(1)//循环判断的作用
{
printf("输入两个数字求最大公约数:");
scanf("%d%d",a,b);
while(a!=b)
{
if(agt;b)
a=a-b;
else
b=b-a;
c++;
}
printf("最大公约数是:%d\n",a);
printf("%d\n",c);
}
return 0;
}
运行效果：
2、辗转相除法：
#includelt;stdio.hgt;
int a,b,temp;
int Division(){
printf("请输入两个数(a,b)：\n");
scanf("%d,%d",a,b);
if(alt;b){
temp=a;
a=b;
b=temp;
}
while(a%b!=0){
temp=a%b;
a=b;
b=temp;
}
printf("最大公约数为：%d\n",b);
return 0;
}
3、穷举法
#includelt;stdio.hgt;
int main()
{
int a,b,c;
int d=0;//计数器
while(1)
{
printf("输入两个数字求最大公约数:");
scanf("%d%d",a,b);
c=(agt;b)?b:a;//三目运算符
while(a%c!=0||b%c!=0)
{
c--;
d++;
}
printf("最大公约数是:%d\n",c);
printf("%d\n",d);
}
return 0;
}
