Goldbach`s Conjecture LightOJ 1259

题目链接:点我

题目

---

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

---

题意:

问一个数n能被表示成两个素数的和的的方式有多少种

思路:

简单的素数打表即可解决,我们枚举每个素数,然后用判断n- 当前素数是否是素数即可.

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;

const int maxn = 1e7 + 10;
bool vis[maxn];
int prim[maxn/10];
int k;

void prime(){
    memset(vis,false,sizeof(vis));
    k = 0;
    for(int i = 2; i <maxn; ++i){
        if(!vis[i]) prim[++k] = i;
        for(int j = 1; j <= k && i * prim[j] < maxn; ++j){
            vis[i * prim[j]] = true;
            if(i % prim[j] == 0)
                break;
        }
    }
}

int main(){
    int t;
    prime();
    scanf("%d", &t);
    int kase = 0;
    while( t--){
        int n;
        scanf("%d", &n);
        int ans = 0;
        int l, r;
        for(int i = 1;prim[i] <= n / 2; ++i)
            if(!vis[n - prim[i]])
                ++ans;
        printf("Case %d: %d\n",++kase, ans);
    }
    return 0;
}