博客

题目描述

有一天蒜头君突发奇想，他有一个猜想，任意一个大于 2的偶数好像总能写成 2 个质数的和。蒜头君查了资料，发现这个猜想很早就被一个叫哥德巴赫的人提出来了，称为哥德巴赫猜想。目前还没有证明这个猜想的正确性。蒜头君告诉你一个整数 n ，让你用这个数去验证。注意 1 不是质数。

输入描述

输入一个偶数n(2<n≤8000000)

输出描述

输出一个整数表示有多少对 (x,y) 满足x+y=n(x≤y) 且x,y 均为质数。

样例输入

6（10）

样例输出

1（2）

AC代码

#include<iostream>
#include<cstring>
using namespace std;
bool is_prime[8000005];
int main()
{
    int n;
    cin>>n;
     for(int i = 2;i<=n;i++){
        is_prime[i] = 1;
    }
    for(int i=2;i*i<=n;i++)
    {
        if(is_prime[i])
        {
            for(int j=i*i;j<=n;j+=i)
            {
                is_prime[j]=0;
            }
        }
    }
    int cnt=0;
    for(int i=2;i<=n/2;i++)
    {
        if(is_prime[i]==1&&is_prime[n-i]==1)
            cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}