请问，如何快速获得N个数的最小公倍数？

Question

已知整数数组a[N]

求a中所有数的最小公倍数
-----------------------------
我现在只知道一个办法，先求出a[0]和a[1]的最小公倍数存到temp中，再
求出temp和a[2]的最小公倍数存到temp中，循环直到求出a中所有数的最小公倍数
----------------------------
但这方法效率太低了，不知道有没有其它更好的方法？
to 自由的菜鸟: 不知我是不是看错了。你的算法好像就是递增一个数，直到找到一个数满足条件？这样好像效率也不高啊？

Answer 1

//方法
此方法把第一个数用来对其它的数求余，然后发现其中有余数不为0的情况下对此数+1，直到对所有的数都取余数为0，则该数为最小公倍数。这个方法时第一个数应该是最大数，这样会更快一些。意思很明确，有人加以修改，将循环中改为将前两个数的公倍数然后继续使用直到得出结果，效果是一样的，效率应该会更高。
#include<stdio.h>
main()
{
int num,i,a[100],d,c;
c=1;
printf("input ji ge zheng shu\n");
scanf("%d",&num);
for(i=0;i<num;i++){
printf("input di %d ge zheng shu\n",i+1);
scanf("%d",&a[i]);
}
d=a[0];
while(c==1){
for(i=0,c=0;i<num;i++){
if(d%a[i]!=0)
{c=1;d++;}
}
}
printf("gong bei shu shi %d",d);
}

--------------------------------------------------------------------------------

2 3 7 8 10 36 的最小公倍数是 2520

把这个算法定义为一个模板，方便重用，如下：
template <class T>
long GetMulLCM(T a[],int num)
{
int c=1;
if(num<=0)return ERROR;
for(int i=0;i<num;i++)
{
if(a[i]<0)return ERROR;
else if(a[i]==0)return 0;
}
T d=a[0];
while(c==1)
{
for(c=0,int i=0;i<num;i++)
{
if(d%a[i]!=0)
{
c=1;
d++;
}
}
}
return (long)d;
}

Answer 2

快速获得最小公倍数的方法：
下次遇到这种情况的时候，无论几个数都可以。 就拿5；9；12来说，先算出来5和9的最小公倍数，这个好算，是45吧，然后算45和12的最小公倍数，共同质数是一个3，然后用45和12相乘，除掉一个3，剩下的就是这三个数的最小公倍数了！

Answer 3

//算法还是这个算法，就是写法简单点
int fun(int *a,int n)
{
if (n==1)
return *a;
else
return fun2(a[n-1],fun(a, n-1));
}
//fun2是求2个数最小公倍数的函数，这个算法就多了
ps:这只是个算法，直接编译当然不能通过

Answer 4

关注。。。
哎，你往上帖代码的时候，好歹自己也编译一下，拿一段编译都通不过的代码上来，还谈什么算法啊 ？

Answer 5

说明下：
对于自由的菜鸟的方法，此方法把第一个数用来对其它的数求余，然后发现其中有余数不为0的情况下对此数+1，直到对所有的数都取余数为0，则该数为最小公倍数。这个方法时第一个数应该是最大数，这样会更快一些。意思很明确，有人加以修改，将循环中改为将前两个数的公倍数然后继续使用直到得出结果，效果是一样的，效率应该会更高。

还有种方法是：
首先输入多个数,把它们存入数组a[N]中,然后求出数组中最大的数a[0],最后用最大的数分别与其他的数求余,如果能与每个数都能求余,则此数为最小公倍数,否则a[0]+=a[0],只到a[0]小于所有数的乘积为止.(几个互为素数的最小公倍数是它们的乘积)。
但是后者的效率不见得是最高的。
后一种方法的程序如下：
#include<stdio.h>
#define N 10
void main()
{
int i,a[N]={0},n,m,t,ji=1;
printf("shu ru suo qiu ge shu\n");
scanf("%d",&n);
printf("shu ru mei ge shu\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
if(a[i]>a[0])
{
t=a[0];
a[0]=a[i];
a[i]=t;
}
for(i=0;i<n;i++)
ji=ji*a[i];
for(m=a[0];m<=ji;m+=a[0])
{
int j=1;
while(j<n)
{
if(m%a[j]==0)
j++;
else
break;
if(j==n)
{printf("zui xiao gong bei shu shi %d\n",m);
goto mm;}
}
}
mm: ;
getch();
}

Answer 6

你是学什么数学的，求最大公倍数？！只有去求最大公约数和最小公倍数的吧。