神马品牌网南昌食尚香培训学校:请教:C语言求最大公约数和最小公倍数
来源：百度文库 编辑：神马品牌网 时间：2024/04/29 08:18:53
我是这么做的,大家看还有什么更简洁的办法没:
最大公约数:
#include<stdio.h>
void main()
{
int m,n,k=1,i;
scanf("%d,%d",&m,&n);
for(i=2;i<=(m>n?n:m);i++)
{
if(m%i==0&&n%i==0)
k=i;
}
printf("The greatest common divisor is %d.\n",k);
}
最小公倍数:
#include<stdio.h>
void main()
{
int m,n,i,k=1,t;
scanf("%d,%d",&m,&n);
if(m>n)
{
t=m;
m=n;
n=t;
}
for(i=m;i<=m*n;i=m*k)
{
if(i%m==0&&i%n==0)
break;
else
k=k+1;
}
printf("The lease common multiple is %d.\n",i);
}
最大公约数:
#include<stdio.h>
void main()
{
int m,n,k=1,i;
scanf("%d,%d",&m,&n);
for(i=2;i<=(m>n?n:m);i++)
{
if(m%i==0&&n%i==0)
k=i;
}
printf("The greatest common divisor is %d.\n",k);
}
最小公倍数:
#include<stdio.h>
void main()
{
int m,n,i,k=1,t;
scanf("%d,%d",&m,&n);
if(m>n)
{
t=m;
m=n;
n=t;
}
for(i=m;i<=m*n;i=m*k)
{
if(i%m==0&&i%n==0)
break;
else
k=k+1;
}
printf("The lease common multiple is %d.\n",i);
}
# include <stdio.h>
long int gcd(long int a,long int b);
void main()
{
long int a,b,mgcd,mlcm;
printf("输入整数a：");
scanf("%d",&a);
printf("输入整数b：");
scanf("%d",&b);
mgcd=gcd(a,b);
mlcm=a*b/mgcd;
cout<<"最大公约数："<<mgcd<<endl<<"最小公倍数："<<mlcm<<endl;
}
long int gcd(long int a,long int b)
{
int temp,fgcd;
if (a < b)
{
temp=a;a=b;b=temp;
}
if (a % b ==0)
{
fgcd=b;
return fgcd;
}
else
{
gcd(b,a % b);
}
}
先用递归求出最大公约数,然后两数相乘除以最大公约数就是最小公倍数了,至于为什么这样自己想想就明白了
调用函数,两个放在一起输出:
main()
{
int m,n;
scanf("%d,%d",&m,&n);
printf("%d %d\n",num(m,n),m*n/num(m,n));
}
int num(int p, int q)
{
if(p<=0||q<=0)return (0);
do{
if (p<q)
{
p=p+q;
q=p;
p=p-q;
}
for(;p>=q;p=p-q);
if (p*q==0)return (p+q);
}
while(1);
}
辗转相除，这种问题见得多了，没必要总是问的，你可以搜一下
先用递归求出最大公约数,
然后两数相乘除以最大公约数就是最小公倍数了
数学问题
欧几里德算法嘛