G5025 [GESP202609 五级] 哥德巴赫猜想 题解

知识点：素数筛、枚举、计数。

解题思路

先筛素数，再枚举i从2到n/2，若i与n-i都是素数则计数。

为什么正确

每种无序拆分有且仅有一个较小加数不超过n/2，枚举覆盖且不重复。

易错点

两素数相同的拆分应计一次；1不属于素数。

复杂度

时间O(n log log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>p(n+1,1);
    p[0]=p[1]=0;
    for(int i=2;i*i<=n;i++)if(p[i])for(int j=i*i;j<=n;j+=i)p[j]=0;
    int ans=0;
    for(int i=2;i<=n/2;i++)ans+=p[i]&&p[n-i];
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。