题目
有一天蒜头君突发奇想，他有一个猜想，任意一个大于 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math>2 的偶数好像总能写成 <math> <semantics> <mrow> <mn> 2 </mn> </mrow> <annotation encoding="application/x-tex"> 2 </annotation> </semantics> </math>2 个质数的和。
蒜头君查了资料，发现这个猜想很早就被一个叫哥德巴赫的人提出来了，称为哥德巴赫猜想。
目前还没有证明这个猜想的正确性。
蒜头君告诉你一个整数 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application/x-tex"> n </annotation> </semantics> </math>n ，让你用这个数去验证。
注意 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 不是质数。
输入格式
输入一个偶数 <math> <semantics> <mrow> <mi> n </mi> <mo> ( </mo> <mn> 2 </mn> <mo> < </mo> <mi> n </mi> <mo> ≤ </mo> <mn> 8000000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> n(2 < n \le 8000000) </annotation> </semantics> </math>n(2<n≤8000000)
输出格式
输出一个整数表示有多少对 <math> <semantics> <mrow> <mo> ( </mo> <mi> x </mi> <mo separator="true"> , </mo> <mi> y </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> (x,y) </annotation> </semantics> </math>(x,y) 满足 <math> <semantics> <mrow> <mi> x </mi> <mo> + </mo> <mi> y </mi> <mo> = </mo> <mi> n </mi> <mo> ( </mo> <mi> x </mi> <mo> ≤ </mo> <mi> y </mi> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> x + y = n(x \le y) </annotation> </semantics> </math>x+y=n(x≤y) 且 <math> <semantics> <mrow> <mi> x </mi> <mo separator="true"> , </mo> <mi> y </mi> </mrow> <annotation encoding="application/x-tex"> x,y </annotation> </semantics> </math>x,y 均为质数。
样例输入
6
样例输出
1
样例输入
10
样例输出
2
题解
这道题想法没问题，判断一个偶数是由多少质数对组成
不过需要筛法优化
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
void prepare(int n){
// 全部标记
for(int i=0;i<=n;i++)
v.push_back(1);
// 筛
for(int i=2;i*i<=n;i++)
if(v[i]) // 如果是质数
for(int j= i*i;j<=n;j+=i)
v[j] = 0;
}
int main(){
int n;
int num = 0;
cin>>n;
prepare(n);
for(int i=3;i<=n/2;i+=2) // 跳过奇数
if(v[i] && v[n-i])
num++;
cout<<num;
return 0;
}
京公网安备 11010502036488号