F - Goldbach`s Conjecture LightOJ - 1259(素数筛）

迷南。 2021-10-29 07:42 222阅读 0赞

# F - Goldbach\`s Conjecture LightOJ - 1259 #

题目链接：[https://vjudge.net/contest/70017\#problem/F][https_vjudge.net_contest_70017_problem_F]

题目：

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

Sample Output

Case 1: 1

Case 2: 1

Note

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

**题意：给你一个偶数，算出多少种a+b=n的可能，其中a,b要是素数且a<b** **思路;素数筛，打表，**

//
    // Created by hanyu on 2019/8/12.
    //
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cctype>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<map>
    #include<stack>
    #include<set>
    #include<vector>
    #include<iostream>
    #include<algorithm>
    typedef long long ll;
    const int maxn=1e7+5;
    using namespace std;
    bool isprime[maxn];
    int prime[maxn/10],pos;
    void getp()
    {
        pos=0;
        memset(isprime,false,sizeof(isprime));
        isprime[0]=isprime[1]=true;
        for(long long i=2;i<maxn;i++){
            if(!isprime[i])
            {
                prime[pos++]=i;
                for(long long j=i*i;j<maxn;j+=i){
                    isprime[j]=true;
                }
            }
        }
    }
    
    int main()
    {
        getp();
        int T,n,kase=1,ans;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&n);
            ans=0;
            for(int i=0;prime[i]<=n/2;i++)
            {
                if(isprime[n-prime[i]]==false)
                    ans++;
            }
            printf("Case %d: %d\n",kase++,ans);
        }
        return 0;
    }

**注意数据范围，我re了很多次。。。。**

转载于:https://www.cnblogs.com/Vampire6/p/11341452.html

[https_vjudge.net_contest_70017_problem_F]: https://vjudge.net/contest/70017#problem/F