F - Goldbach`s Conjecture kuangbin 基础数论

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 10 ⁷ .

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 ⁷ , 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

Hint

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

2. #include<iostream>
   
   #include<cstdio>
   
   #include<cmath>
   
   #include<cstring>
   
   #include<sstream>
   
   #include<algorithm>
   
   #include<queue>
   
   #include<deque>
   
   #include<iomanip>
   
   #include<vector>
   
   #include<cmath>
   
   #include<map>
   
   #include<stack>
   
   #include<set>
   
   #include<fstream>
   
   #include<memory>
   
   #include<list>
   
   #include<string>
   
   using namespace std;
   
   typedef long long LL;
   
   typedef unsigned long long ULL;
   
   #define MAXN 10000001
   
   #define L 31
   
   #define INF 1000000009
   
   #define eps 0.00000001
   
   /*
   
   打表 把所有素数存到一个vector中
   
   然后用一个map保存所有和出现的次数
   
   然后直接找就可以
   
   */
   
   bool notprime[MAXN];
   
   vector<int> prime;
   
   void Init()
   
   {
   
       memset(notprime, false, sizeof(notprime));
   
       notprime[] = true;
   
       for (int i = ; i < MAXN; i++)
   
       {
   
           if (!notprime[i])
   
           {
   
               prime.push_back(i);
   
               for (int j = i + i; j < MAXN; j += i)
   
                   notprime[j] = true;
   
           }
   
       }
   
   }
   
   int main()
   
   {
   
       Init();
   
       int T,n;
   
       cin >> T;
   
       for(int cas=;cas<=T;cas++)
   
       {
   
           cin >> n;
   
           vector<int>::iterator p = lower_bound(prime.begin(), prime.end(), n/);
   
           //cout << *p << endl;
   
           int cnt = ;
   
           for (vector<int>::iterator it = prime.begin(); it <= p && *it<=n/; it++)
   
           {
   
               if (!notprime[n - *it])
   
               {
   
                   //cout << *it << ' ' << n - *it << endl;
   
                   cnt++;
   
               }
   
           }
   
           printf("Case %d: %d\n", cas, cnt);
   
       }
   
       return ;
   
   }