作者tw00088437 (喵猫 loves fish)
看板C_and_CPP
标题[ACM ] 建表过程中就已经TLE了@@?
时间Sat Oct 31 21:56:06 2009
题目
http://zerojudge.tw/ShowProblem?problemid=d419
遇到的问题：
尝试先建质数表 再建每个数质因数数量的表
但是建到一百万好像就已经TLE了@@
有问题的code： (请善用置底文的标色功能)
code如下
上半部建质数表再丢到store阵列里面去
中半部先算出每个数的质因数数目
下半部才是接受输入的数目并把所有2~n的质因数数目加起来
请问哪里可以改进效率避免TLE呢@@
#include<iostream>
using namespace std;
bool prime[1000000]={1,1,0,0};
int store[78500]={0};
int storeans[1000000]={0};
int a,b,c,d,i,h,g,n,k,l,j;
int main()
{
for(a=4;a<1000000;a+=2)
prime[a]=1;
for(a=6;a<1000000;a+=3)
prime[a]=1;
d=0;
for(a=5;a<1000000;a=a+d%2*2+2,d++)
{
if(prime[a]==0)
{
b=a;
while(b+a<1000000)
{
b+=a;
prime[b]=1;
}
}
else
continue;
}
c=0;
for(a=0;a<1000000;a++)
{
if(prime[a]==0)
{
store[c]=a;
c++;
}
}
for(a=2;a<=1000000;a++)
{
l=0;
for(j=0;j<1000;j++)
{
if(a%store[j]==0)
{
storeans[a]=storeans[a/(store[j])]+1;
l=1;
break;
}
}
if(l)
continue;
h=0;
k=a;
c=0;
while(k!=1)
{
while(k%store[c]==0)
{
k/=store[c];
h++;
} //end inner while
c++;
} //end second while
storeans[a]=h;
}
while(cin>>n)
{
g=0;
for(a=2;a<=n;a++)
{
g+=storeans[a];
}
cout<<g<<endl;
} //end outer while
return 0;
}
补充说明：
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.97.60
1F：→ netsphere:这可以用DP加速 10/31 22:05
2F：→ bleed1979:6n+-1配合筛法建质数表 10/31 22:15
3F：→ tw00088437:a=a+d%2*2+2,d++ <---我有用6n+-1啊@@" 10/31 22:18
4F：→ tw00088437:请问1楼 DP是?? 10/31 22:19
5F：→ bleed1979:a[2]=1 a[2*2]=1+1 a[2*2*2]=a[2*2]+1 10/31 22:20
6F：→ tw00088437:storeans[a]=storeans[a/(store[j])]+1 <--请问楼上是 10/31 22:21
7F：→ tw00088437:指这个吗@@? 10/31 22:21
8F：→ janice001:动态规划 10/31 22:57
9F：→ tw00088437:@@? 10/31 23:22
11F：→ tw00088437:噢噢大致看懂了 感谢: ))) 11/01 00:33
12F：→ tw00088437:不过inline 还有int main()里面的东西不太了解 11/01 00:33
13F：→ tw00088437:还没学到 可以稍微解释一下吗^^" 11/01 00:33
14F：推 cplusplus:先自己上网或看书会不会比较有诚意一点...? 11/01 01:53
15F：→ bleed1979:其实方法大致和推文的程式码一样，只是应该不需用到% 11/01 10:19
16F：→ bleed1979:以下程式码速度大概快一倍 11/01 10:19
18F：→ tw00088437:看懂了 谢谢^^" 11/01 11:46