公倍数
时间： 1ms 内存：128M
描述：
为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。我们希望寻找到能除尽1至n的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。
输入：
6
输出：
60
示例输入：
10示例输出：
2520提示：
参考答案（内存最优[1092]）：
#include<cstdio>
int n;
int a[105];
int sum=1;
int b[105];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
b[i]=i;
}
for(int i=2;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(b[j]%b[i]==0)
b[j]=b[j]/b[i];
}
}
a[1]=1;
for(int i=2;i<=n;i++)
{
int k=0;
for(int j=1;j<=sum;j++)
{
int t=a[j]*b[i]+k;
a[j]=t%10000;
k=t/10000;
}
while(k)
{
sum++;
a[sum]=k%10000;
k/=10000;
}
}
printf("%d",a[sum]);
for(int i=sum-1;i>=1;i--)
{
printf("%04d",a[i]);
}
return 0;
} 参考答案（时间最优[0]）：
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int a[100]={1};
int i,j;
int len=1;
int wait[100];
int kwait=0;
int jinwei(int [],int);
int cheng(int [],int,int);
bool prime(int);
int n;
cin>>n;
if(n==1)
{
cout<<1<<endl;
return 0;
}
for(i=2;i<=n;i++)
{
if(prime(i))
{
wait[kwait++]=i;
len=cheng(a,i,len);
}
else
{
int count=i;
for(j=0;j<kwait;j++)
{
if(count%wait[j]==0)count/=wait[j];
if(count==1)break;
}
if(j==kwait) //寻找失败，必须再凑个因数 而这个因数便是count
{
wait[kwait++]=count;
len=cheng(a,count,len);
}
}
}
for(i=len-1;i>=0;i--)
{
cout<<a[i];
}
cout<<endl;
return 0;
}
int jinwei(int a[],int len) //注意存放时以下标为0的为个位 方便进位
{
int i;
for(i=0;i<len+1;i++) //最多×100 所以最多进2位
{
if(a[i]>=10)
{
a[i+1]+=a[i]/10;
a[i]%=10;
}
}
if(a[len+1]!=0)return len+2; // 2 7 7
if(a[len]!=0)return len+1;
return len;
}
int cheng(int a[],int n,int len)
{
int i;
for(i=0;i<len;i++)
{
a[i]*=n;
}
len=jinwei(a,len);
return len;
}
bool prime(int n)
{
if(n==1)return false;
if(n==2)return true;
if(n%2==0)return false;
if(n==3)return true;
if(n%3==0)return false;
if(n==5)return true;
if(n%5==0)return false;
int i;
for(i=7;i<n;i++)
{
if(n%i==0)break;
}
if(i==n)return true;
else return false;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。