[ACM ] 建表過程中就已經TLE了@@?
題目
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
→
10/31 22:05, , 1F
10/31 22:05, 1F
→
10/31 22:15, , 2F
10/31 22:15, 2F
→
10/31 22:18, , 3F
10/31 22:18, 3F
→
10/31 22:19, , 4F
10/31 22:19, 4F
→
10/31 22:20, , 5F
10/31 22:20, 5F
→
10/31 22:21, , 6F
10/31 22:21, 6F
→
10/31 22:21, , 7F
10/31 22:21, 7F
→
10/31 22:57, , 8F
10/31 22:57, 8F
→
10/31 23:22, , 9F
10/31 23:22, 9F
→
10/31 23:36, , 10F
10/31 23:36, 10F
→
11/01 00:33, , 11F
11/01 00:33, 11F
→
11/01 00:33, , 12F
11/01 00:33, 12F
→
11/01 00:33, , 13F
11/01 00:33, 13F
推
11/01 01:53, , 14F
11/01 01:53, 14F
→
11/01 10:19, , 15F
11/01 10:19, 15F
→
11/01 10:19, , 16F
11/01 10:19, 16F
→
11/01 10:20, , 17F
11/01 10:20, 17F
→
11/01 11:46, , 18F
11/01 11:46, 18F