求两个正整数的最大公约数和最小公倍数

我一个新手对这个程序的算法不是很明白啊....
想请教一下各位啊....
先在此谢谢大家了....

17 个解决方案

#1

http://topic.csdn.net/t/20050822/17/4224031.html

#2

百度一下就一大堆

#3

两个自然数的积除以它们的最大公约数就是最小公倍数。所以，只要求出最大公约数即可。
求最大公约数，简单一点的方法可以用穷举法，从小的数开始，从大到小把每一个小于它们的数都测一下，第一个找到的就是。
快一点的方法是“辗转相除法”，方法的步骤和正确性证明可以找一本数论的书来看看，当然最简单的方法还是google“辗转相除法”。

#4

告诉你思路吧，还是自己写好：
最小公倍数：如果a,b都不是多个数乘出来的，那a*b就是最小公倍数,如果其中a是多个数乘出来的，b不是，那就把b乘上a的各个因数，a,b都是乘出来的同理，就是挨着乘.......反正我是这么想的。

最大公约数：如果俩个数有最小公约数，分别比各个因子，最大的就是

因子就是4=2x2,2就是因子；6=2x3x1,1，2，3都是因子
你弄个循环然后去比就行了

#5

碾转相除法。
公式：(m,n)=(n,m%n)
方法一：
#include <stdio.h>

int main()
{
int m, n, r = 1;
scanf("%d%d", &m, &n);
while (r != 0)
{
r = m % n;
m = n;
n = r;
}
printf("%d", m);
return 0;
}

方法二：还有一个利用条件运算符写的求最大公约数程序代码

#include<stdio.h>

int main()
{
int m, n;
scanf("%d%d", &m, &n);
while(m > n ? (m = m % n) : (n = n % m));
printf("%d", m + n);
return 0;
}

#6

我顶楼上，不愧为高手！
#include <iostream>
using namespace std;

int main()
{
int m, n, m1, n1, r = 1;
cin>>m>>n;

m1=m;
n1=n;

while (r != 0)
{
r = m % n;
m = n;
n = r;
}
cout<<"最大公约数："<<m<<endl;
cout<<"最小公倍数："<<m1*n1/m<<endl;

system("pause");
return 0;
}

#7

//修改一下
#include <iostream>
using namespace std;

int main()
{
int m, n, m1, n1, r = 1;
cin>>m>>n;

if(m<n)
{
   m1=m;
   m=n;
   n=m1;
}
m1=m;
n1=n;

while (r != 0)
{
r = m % n;
m = n;
n = r;
}
cout < <"最大公约数：" < <m < <endl;
cout < <"最小公倍数：" < <m1*n1/m < <endl;

system("pause");
return 0;
}

#8

引用 5 楼 breezes2008 的回复:

方法二：还有一个利用条件运算符写的求最大公约数程序代码

#include <stdio.h>

int main()
{
int m, n;
scanf("%d%d", &m, &n);
while(m > n ? (m = m % n) : (n = n % …

这个赞

#9

首先找到最大公约数，在用两数之积除去最大公约数后就得到是最小公约数，
如：main()
{int a,b,num1,num2,temp;
scanf("%d,%d",&num1,&num2);
if(num1<num2){temp=num1;num1=num2;num2=temp;}
a=num1;b=num2;
while(b!=0)
   {temp=a%b;
    a=b;
    b=temp;}
printf("%d\n",a);
printf("%d\n",num1*num2/a);
}
或者用辗转相除法，也可以这种自己去网上查查！

#10

用欧几里得扩展算法～

#11

凭记忆写个



gcd(a,b)

{

   if(b ==1)

      return a;

   return gcd(b,a%b));

}


最大公倍数 a*b/gcd(a,b)

#12

帮忙顶一下，这种题在网上能搜者的，最好自己写啦

#13

辗转相除就这个，好好研究一下！！

#14

引用 6 楼 yangxd1982 的回复:

我顶楼上，不愧为高手！
#include <iostream>
using namespace std;

int main()
{
int m, n, m1, n1, r = 1;
cin>>m>>n;

m1=m;
n1=n;

while (r != 0)
{
r = m % n;
m = n;
n = r;
}
cout < <"最大公约数：" < <m < <endl;
cout < <"最小公倍数：" < <m1*n1/m < <endl;

system("pause");
return 0;
}

两个算法都很好。。。

#15

<< 这个位移有些书里都不讲了呢..

#16

学习一下，增长一点算法知识。

#17

辗转相除法在数比较大的时候，其中的取模操作符的开销比较昂贵
可以考虑做差来做，但是做差时如果两数相差太大，循环次数很大
最后，可以用做差和素数的理论来做。

#1