作者topgod12 (無名)
看板C_and_CPP
標題[ACM ] 10394
時間Sat Jun 13 12:26:11 2009
上傳一直都過不了，常Time limit exceeded
不知有沒有什麼好方法可以加速
目前想到的是查表
可是一直建不起來，如下段程式碼所述
有人知道此題的 Time Limit 是多少，網址上說30S
http://acm.uva.es/p/v103/10394.html
可是上傳3S就回TLE
Problem Verdict Language Run Time
Twin Primes Time limit exceeded C++ 3.000
麻煩各位了！
程式碼
#include<iostream>
#include<vector>
#define N 20000000
#define SIZE 100000
using namespace std;
int main()
{
int i,k,prime,twin=0,s;
vector<bool> sieve(N+1);
vector<int> twinprime(SIZE);
for(i=2;i<=N;i++)
sieve[i]=true;
sieve[0]=false;
sieve[1]=false;
for(i=1;i<=N;i++)
{
if(sieve[i])
{
prime=i;
for(k=prime+i;k<=N;k+=prime)
{
sieve[k]=false;
}
}
}
//底下這段一直想用建查表法，可是不知是否因陣列太大而runtime error
//ex： cout<<'('<<twinprime[s]<<", "<<twinprime[s]+2<<")\n";
//改成上述又Time limit exceeded
while(cin>>s)
{
twin=0;
for(i=2;i<=N;i++)
if(sieve[i] && sieve[i+2])
{
twin++;
if(twin==s)
cout<<'('<<i<<", "<<i+2<<")\n";
}
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.139.142.179
1F：推 cismjmgoshr:這題的時限是3秒，在UVa題目頁面左上角有寫。 06/13 16:44
2F：→ cismjmgoshr:20000000以下的twin prime有107407組，runtime error 06/13 16:56
3F：→ cismjmgoshr:會不會是因為陣列只開到100000，不夠存? 06/13 16:57
4F：→ topgod12:感謝C大終於AC，我忘記陣列的問題了！ 06/14 00:03