公倍数

公倍数

时间: 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;
}  

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注