本文共 1802 字，大约阅读时间需要 6 分钟。

欧拉筛：利用每个最小质因子筛掉合数，并且不会重复筛到。

题：

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].

Your task is to check whether this conjecture holds for integers up to 10^7.

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 ≤ 10^7, 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:

Both a and b are prime,

a + b = n and 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。 输入整数n。 条件：a+b=n并且a<=b并且a、b都是素数。 找出有多少个这样的成立。

#include
   
    using namespace std;const int maxn = 7e6;const int N=1e7+5;long prime[maxn],countnum =0;	//prime数组记录素数，countnum记录素数个数 bool p[N]={   false};void isprime()	//查找记录2到n的素数 {   	long long i,j;	for(i=2;i<=N;++i)	{   		if(p[i]==false)	//如果未被筛过，则为素数 			prime[countnum++]=i;		for(j=0;j
    
     N)	//当要标记的合数超出范围时跳出 				break;							p[i*prime[j]]=true;	//将已经记录的素数的倍数进行标记 						if(i%prime[j]==0)					break; 							//当i是prime[j]的整数倍时			//记 m = i / prime[j]			//那么 i * prime[j+1] 就可以变为 (m * prime[j+1]) * prime[j]			//这说明 i * prime[j+1] 是 prime[j] 的整数倍			//不需要再进行标记(在之后会被 prime[j] * 某个数 标记)			//对于 prime[j+2] 及之后的素数同理，直接跳出循环，这样就避免了重复标记。		}	}}int main(){   	int t,o=0;	cin>>t;	isprime();	while(t--)	{   		o++;		long long n,s=0;		cin>>n;		for(int i=0;prime[i]<=n/2;++i)		{   			if(p[n-prime[i]]==false)			{   				s++;			}		}		cout<<"Case "<
     
      <<": "<
      <