Goldbach’s conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:
Every even integer, greater than 2, can be expressed as the sum of two primes [1].
Now your task is to check whether this conjecture holds for integers up to 107.
Input
Input starts with an integer T (≤ 300), denoting the number of test cases.
Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).
Output
For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where
1 : Both a and b are prime
2 : a + b = n
3 : a ≤ b
Sample Input
2
6
4
Sample Output
Case 1: 1
Case 2: 1
Note
1: An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, …
题目大意：
输入 t 表示有 t 组测试样例，对于每个测试样例输入一个数，我们要做的是把这个数分解成两个数ab，其中ab有要求，ab必须是素数，a必须<=b，a+b必须等于这个数，求符合这三个条件的方案数。
解题思路：
这个题很明显我们要把1e7以内的素数先筛出来，并用另一个数组存放每一个素数，PS：存素数的数组一定要够大，因为这个点RE了一次。然后从第一个素数遍历到数字n即可，注意的是停止条件是2 x 当前的数<=n，因为要求a+b，而边界情况是a=b，所以遍历到n/2即可。判断一下n-当前的数是不是素数，如果是ans++，最后输出ans即可。AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
const int _max=1e7+50;
bool book[_max];
int prime[1000050],cnt=0,a;//prime一定要够大！！
void init()//晒素数
{
memset(book,false,sizeof book);
for(int i=2;i<_max;i++)
{
if(!book[i])
{
prime[cnt++]=i;
for(int j=i*2;j<_max;j+=i)
book[j]=true;
}
}
}
int main()
{
ios::sync_with_stdio(false);
int t,k=1;
cin>>t;
init();
while(t--)
{
cin>>a;
int ans=0;
for(int i=0;i<cnt&&prime[i]*2<=a;i++)
if(!book[a-prime[i]])//判断一下这两个数是不是都是素数,因为a一定<=b且a+b一定等于n。
ans++;
cout<<"Case "<<k++<<": "<<ans<<endl;
}
//system("pause");
return 0;
}