13518219792
#includestdio.h
创新互联公司专注于桓仁网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供桓仁营销型网站建设，桓仁网站制作、桓仁网页设计、桓仁网站官网定制、小程序设计服务，打造桓仁网络公司原创品牌,更为您提供桓仁网站排名全网营销落地服务。
intfun(intm,intn);
intfun1(intm,intn);
voidmain(){
intm,n;
do{
scanf("%d%d",m,n);
}while(m=0||n=0);
printf("%d,%d最大公约数是%d\n",m,n,fun(m,n));
printf("%d,%d最小公倍数是%d\n",m,n,fun1(m,n));
}
intfun(intm,intn){
intr,t;
if(mn){
t=m;m=n;n=t;
}
while(n!=0){//辗转相除法
r=m%n;
m=n;
n=r;
}
returnm;
}
intfun1(intm,intn){//暴力破解法
intresult;
for(result=1;;result++){
if(result%m==0result%n==0){
break;
}
}
returnresult;
}
扩展资料
c语言求两个整数的最大公约数
#includestdio.h
#includestdlib.h
intmain()
{
inttmp,a,b;
printf("请输入两个整数:\n");
scanf("%d%d",a,b);
while(a%b!=0)
{
tmp=a%b;//取余
a=b;//交换a，b可避免a比b小
b=tmp;
}
printf("%d\n",b);
return0;
}
以下是求两个数最大公因数的C语言函数。
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
你是对原理不清楚吗？
这个求最大公因数的算法是欧几里得算法，其原理是gcd(a,b)=gcd(b,a%b)，不断辗转相除，到最后一个数变成了0，那么gcd(a,0)=a，就求出了gcd。
例如：gcd(12,15)=gcd(15,12%15)=gcd(15,12)=gcd(12,15%12)=gcd(12,3)=gcd(3,12%3)=gcd(3,0)=3。
证明可以查阅相关资料，属于数论范畴，这里不赘述。
然后是最小公倍数，原理是lcm(a,b)=a*b/gcd(a,b)，因为公因数被算了两遍，所以要除掉。
例如：lcm(12,15)=12*15/3=60。
所以代码的意思就是：
s = m * n; // 计算出两个数的乘积，稍后用于计算lcm
// 计算最大公因数
while (n != 0) // 判断是否到达 gcd(m, 0) 的情况
{
// 从 gcd(m, n) 变为 gcd(n, r)，即 gcd(n, m % n)
r = m % n;
m = n;
n = r;
}
// 现在是 n = 0，所以 gcd(m, 0) = m
printf("GCD: %d\n", m);
// 计算 lcm，即原来两数的乘积 s 除以最大公因数 m
printf("LCM: %d\n\n", s / m);
希望对你有帮助，谢谢！
第一步：比较两数大小
第二步：用大数除以小数取余，如果为零，则最大公因数为小数
第三步：循环
｛用大数（a)除以小数(b)减i++(i初值为0)取余，如果余数不为零，则用小数除以小数减i，为零则表示小数减i就是最大公因数，否则重新循环，结束循环的条件是i=小数(b)
｝
