[ACM ] 10394
上傳一直都過不了,常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
推
06/13 16:44, , 1F
06/13 16:44, 1F
→
06/13 16:56, , 2F
06/13 16:56, 2F
→
06/13 16:57, , 3F
06/13 16:57, 3F
→
06/14 00:03, , 4F
06/14 00:03, 4F