最小公倍数
时间限制:
1000?ms ?|? 内存限制:
65535?KB
难度:
3
-
描述
-
为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。
但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。
事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数m.
-
输入
-
多组测试数据(少于500组)。
每行只有一个数n(1<=n<=100).
-
输出
-
输出相应的m。
-
样例输入
-
2
3
4
-
样例输出
-
2
6
12
-
来源
-
2011蓝桥杯
-
上传者
-
ACM_杨延玺
ac代码
#include<stdio.h>
#include<string.h>
int pri[110];
int ans[110][50];
void prime()
{
int i;
for(i=2;i<110;i++)
{
if(!pri[i])
{
for(int j=i+i;j<110;j+=i)
pri[j]=1;
}
}
}
void fun()
{
int a,i,j,k;
for(a=3;a<=100;a++)
{
ans[a][0]=1;
for(i=2;i<=a;i++)
{
if(pri[i]==0)
{
j=i;
while(j<=a)
{
j*=i;
int temp=0;
for(k=0;k<50;k++)
{
int num=ans[a][k]*i+temp;
// if(!num)
// break;
ans[a][k]=num%10;
temp=num/10;
}
}
}
}
}
}
int main()
{
prime();
fun();
int n;
while(scanf("%d",&n)!=EOF)
{
int i;
if(n==1||n==2)
{
printf("%dn",n);
}
else
{
for(i=49;i>=0;i--)
{
if(ans[n][i])
break;
}
for(;i>=0;i--)
{
printf("%d",ans[n][i]);
}
printf("n");
}
}
}
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|