Question

一道简单的ACM题，总是超时，高手帮忙看看吧。

http://acm.hrbeu.edu.cn/index.php?act=problem&id=1060

我的代码：
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
for(int i=2;i<=sqrt(double(n));i++)
if(n%i==0)
return false;
return true;
}
int main()
{
int n;
while(cin>>n)
{
if(n==0)
break;
for(int i=3;i<=n/2;i++)
if(isPrime(i)&&isPrime(n-i))
{
cout<<n<<" "<<"="<<" "<<i<<" "<<"+"<<" "<<n-i<<endl;
break;
}
}
return 0;
}

Answer 1

1.事先将1000000以内的所有素数算出来，放到数组vector<int>Prime里。不要每次都重复运算。
2.之后暴搜就行了，也就是for(int i = 3; i <= n/2; i++)改成for(int i = 0; i < Prime.size() && Prime[i] <= n/2; i++)。