首页 > 代码库 > F - Goldbach`s Conjecture kuangbin 基础数论

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

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[1] = true;
        for (int i = 2; 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=1;cas<=T;cas++)
        {
            cin >> n;
            vector<int>::iterator p = lower_bound(prime.begin(), prime.end(), n/2);
            //cout << *p << endl;
            int cnt = 0;
            for (vector<int>::iterator it = prime.begin(); it <= p && *it<=n/2; it++)
            {
                if (!notprime[n - *it])
                {
                    //cout << *it << ‘ ‘ << n - *it << endl;
                    cnt++;
                }
            }
            printf("Case %d: %d\n", cas, cnt);
        }
        return 0;
    }

     

F - Goldbach`s Conjecture kuangbin 基础数论