Question

谁能帮解答下 编程题 1.输入两个正整数m和n，求其最大公约数和最小公倍数。

Answer 1

#include <stdio.h>
#include<iostream.h>
void main()
{ int m,n,i,j,mn,a,x,y;
printf("请输入m,n\n");
scanf("%d%d",&m,&n);
mn=m*n;
a=(m<n)?m:n;
for (i=2;i<a;i++)
{ if (m%i==0 && n%i==0)
x=i;
}
printf("m和n的最大公约数是%d\n",x);
for (j=mn;j>=((m>n)?m:n);j--)
{ if (j%m==0 && j%n==0)
y=j;
}
printf("m和n的最小公倍数是%d\n",y);
}

Answer 2

int fun1(int m,int n)
{
while(m!=n)
{
if(m>n) m=m-n;
else n=n-m;
}
return (m);

}
跟你讲讲辗转相除法的原理。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

Answer 3

用c++实现如下：
#include
void
main()
{
int
a,b,c,d;
cout<<"请输入两个数"<
>a>>b;
d=a*b;
while(c=a%b)
{
a=b;
b=c;
}
cout<<"最大公约数为"<
void
main()
{
int
a,b,c,d;
printf("请输入两个数\n");
scanf("%d%d",&a,&b);
d=a*b;
while(c=a%b)
{
a=b;
b=c;
}
printf("最大公约数为%d\n",b);
printf("最小公倍数为%d\n",d/b);
}
备注：最小公倍数等于两个数的乘积除以最小公约数

Answer 4

用c++实现如下：
#include<iostream.h>
void main()
{
int a,b,c,d;
cout<<"请输入两个数"<<endl;
cin>>a>>b;
d=a*b;
while(c=a%b)
{
a=b;
b=c;

}
cout<<"最大公约数为"<<b<<endl;
cout<<"最小公倍数为"<<d/b<<endl;

}
用c语言实现如下：
#include<stdio.h>
void main()
{
int a,b,c,d;
printf("请输入两个数\n");
scanf("%d%d",&a,&b);
d=a*b;
while(c=a%b)
{
a=b;
b=c;

}
printf("最大公约数为%d\n",b);
printf("最小公倍数为%d\n",d/b);

}
备注：最小公倍数等于两个数的乘积除以最小公约数

Answer 5

#include <stdio.h>

int gcd(int a,int b){ // 求最大公约数。
if ( b==0 ) return a;
return gcd(b,a%b);
}

int main(){
int m,n,GcdResult;
scanf("%d%d",&m,&n); //输入。
GcdResult=gcd(m,n);//主过程。
printf("Gcd is %d\nLcm is %d\n",GcdResult,n*m/GcdResult);//输出
return 0;
}

辗转相除法.
ps: 1. 二楼的太慢，并且是辗转相减法。可以用，更改一下，改成递归，并且
当m n为偶数时整除2，时间为log2(n).
2.gcd() // 即本程序 时间复杂度为斐伯那契数列的反函数。