Question

如何用C语言求两个数的最大公约数的三种算法

Answer 1

1、相减法

#include<stdio.h>

int main()

{

int a,b;

int c=0;//计数器

while(1)//循环判断的作用

{

printf("输入两个数字求最大公约数:");

scanf("%d%d",&a,&b);

while(a!=b)

{

if(a>b)

a=a-b;

else

b=b-a;

c++;

}

printf("最大公约数是:%d\n",a);

printf("%d\n",c);

}

return 0;

}

运行效果：

2、辗转相除法：

#include<stdio.h>

int a,b,temp;

int Division(){

printf("请输入两个数(a,b)：\n");

scanf("%d,%d",&a,&b);

if(a<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、穷举法

#include<stdio.h>

int main()

{

int a,b,c;

int d=0;//计数器

while(1)

{

printf("输入两个数字求最大公约数:");

scanf("%d%d",&a,&b);

c=(a>b)?b:a;//三目运算符

while(a%c!=0||b%c!=0)

{

c--;

d++;

}

printf("最大公约数是:%d\n",c);

printf("%d\n",d);

}

return 0;

}

Answer 2

用辗转相除法来求。
<1> 用辗转相除法求最大公约数
算法描述:
m对n（在这里，m>n）求余为r, 若r不等于0
则 m <- n, n <- r, 继续求余
否则 n 为最大公约数
<2> 最小公倍数 = 两个数的积 / 最大公约数
程序：
#include "stdio.h"
main()
{
int m,n,num1,num2,r,cup;
scanf("%d,%d",&num1,&num2);
if(num1<num2)
{
cup=num1;
num1=num2;
num2=cup;
}
m=num1;
n=num2;
r=m%n;
while(r)
{
m=n;
n=r;
r=m%n;
}
printf("zui da gong yue shu shi:%d\n",n);
printf("zui xiao gong bei shu shi:%d\n",num1*num2/n);
}
**********************************************
用辗转相除法求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
例如求1515和600的最大公约数，
第一次：用600除1515，商2余315；
第二次：用315除600，商1余285；
第三次：用285除315，商1余30；
第四次：用30除285，商9余15；
第五次：用15除30，商2余0。
1515和600的最大公约数是15。
辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。
希望可以帮到您，谢谢！