作者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