C语言求最大公因数和最小公倍数的N种方法?

发布网友发布时间：2022-04-24 02:39

共3个回答

热心网友时间：2023-07-29 06:22

（A）
#include<stdio.h>

int f(int a,int b,int n)
{if(a%n+b%n) n=f(a,b,n-1);
return n;
}

void main()
{int a,b,t,n,m;
printf("input a,b:\n");
scanf("%d%d",&a,&b);
n=(a>b)?b:a;
m=a*b/f(a,b,n);
printf("zui da gong yue shu:%d\nzui xiao gong bei shu:%d\n",f(a,b,n),m);
}

（B）
把上面的递归换成循环
#include<stdio.h>
void main()
{
int x,y,a,m,n,t;
printf("please input two num x,y\n");
scanf("%d%d",&x,&y);
for(a=x>y?x:y;a>0;a--)
if(x%a==0&&y%a==0)
{
printf("x,y最大公约数 %d\n",a);
break;
}
m=x/a;
n=y/a;
t=a*m*n;
printf("x,y最小公倍数 %d\n",t);
}

（C）
辗转相除法，这才是最好的方法，一定要掌握
http://ke.baidu.com/view/255668.html?wtp=tt
有了大公约，两数乘后除以大公约即为小公倍

热心网友时间：2023-07-29 06:23

我只知道有一种叫辗除法求最大公因数，详细过程请看：
http://ke.baidu.com/view/2434272.htm

求出最大公因数后，
利用：最小公倍数=A*B/最大公因数。

热心网友时间：2023-07-29 06:23

这个我作个记号我也想看看高手的算法