版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/44163723

Goldbach`s Conjecture

Time Limit: 2000 MS Memory Limit: 32768 KB 64bit IO Format: %lld
& %llu

Submit Status

Description

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

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

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#include <time.h>
#include <queue>
#include <iterator>

using namespace std;

int t;
const int MAXN = 10000010;

bool com[MAXN];
int primes, prime[MAXN/10];//数组不必开的太大

void solve(int n)
{
    primes = 0;
    memset(com,false,sizeof(com));
    com[0] = com[1] = true;
    for (int i = 2; i <= n; ++i)
    {
        if (!com[i])
        {
            prime[++primes] = i;
        }
        for (int j = 1; j <= primes && i*prime[j] <= n; ++j)
        {
            com[i*prime[j]] = true;
            if (!(i % prime[j]))
                break;
        }
    }
}

int main()
{
    solve(10000000);
    int t, cases = 1, n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d", &n);


        int ans = 0;
        for (int i = 1; prime[i] * 2 <= n; i++)//效率高
        {
            if (!com[n - prime[i]])
                ans++;
        }
        printf("Case %d: %d\n", cases++, ans);
    }
    return 0;
}