NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 27 题

完善程序： （哥德巴赫猜想）哥德巴赫猜想是指，任一大于 $2$ 的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于 $2$ 且不超过 $n$ 的偶数都能写成两个质数之和。

#include <iostream>
using namespace std;

int main()
{
    const int SIZE = 1000;
        
    int n, r, p[SIZE], i, j, k, ans;
    bool tmp;
    
    cin>>n;
    r = 1;
    p[1] = 2;
    for (i = 3; i <= n; i++) {
        [    ①    ];
        for (j = 1; j <= r; j++)
            if (i % [     ②   ]  == 0) {
                tmp = false;
                break;
            }
        if (tmp) {
            r++;
            [    ③   ] ;
        }
    }
    
    ans = 0;
    for (i = 2; i <= n / 2; i++) {
        tmp = false;
        for (j = 1; j <= r; j++)
            for (k = j; k <= r; k++)
                if (i + i == [     ④   ] ) {
                    tmp = true;
                    break;
                }
        if (tmp)
            ans++;
    }
    cout<<a

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是筛质数再验证哥德巴赫猜想。先理清数组p存的是前r个质数，筛数时tmp默认true，若被p[j]整除则tmp变false；验证时只要找到一对p[j]+p[k]==2i即可计数。

最容易翻车的是把tmp初始化成0或false，那样所有数都会被判定为合数；还有把p[r]=i写成p[r-1]=i，导致数组越界或数据错位；验证循环里把i+i写成i*2虽然等价，但原题填空是i+i，改了就扣分；最后输出ans时忘了题目问的是“验证成功”的标志，其实是输出ans本身，别被题干绕晕去算其他值。

这道题考查的是质数筛选（埃拉托斯特尼筛法的简化版）和哥德巴赫猜想的程序验证，核心就是先筛出n以内所有质数存进数组p，再遍历每个偶数看能不能拆成两个质数和。命题人喜欢挖这种细节坑：数组下标从1开始存质数，p[1]=2，后面r表示当前已筛出的质数个数，tmp用来标记当前i是不是质数。拿到题先想清楚流程：外层for(i=3;i<=n;i++)筛数，内层j从1到r用已有的质数试除，若能整除说明i是合数，tmp变false并break；如果tmp保持true，说明i是质数，r加1并把i存入p[r]。这里填空①就是tmp的初值，必须是true（或1），否则后续逻辑全崩；填空②是试除的除数，自然是p[j]；填空③是存新质数，p[r]=i。

筛完质数后，验证哥德巴赫猜想：题目要求对每个大于2且不超过n的偶数验证，偶数可以写成2*i的形式，i从2到n/2。对每个2*i，我们需要判断是否存在两个质数p[j]和p[k]（j<=k）使得p[j]+p[k]==2*i。代码里用了三重循环，前两层枚举j和k，第三层判断和，填空④就是p[j]+p[k]（或p[k]+p[j]，加法交换律不影响）。只要tmp变true就break，然后ans++。

最后输出ans。题目问“输出[ ]时表示验证成功”，意思就是输出ans的值。n=2010时，2到2010的偶数共有1005个（2,4,...,2010），其中2本身不能拆成两个大于等于2的质数和（2=1+1但1不是质数），所以实际需要验证的偶数是4到2010，共1004个。根据哥德巴赫猜想（在2010以内已被验证成立），这1004个偶数都能拆成两个质数和，因此ans=1004。填空⑤就是1004。

考频与趋势：质数与合数在题库里共考过52题，覆盖7个级别，其中NOIP普及组初赛仅1题，说明这类“完善程序+数论”的题在普及组不常考，但一旦出现就是重头戏。循环结构考得最多（609题），基础算法30题，整数与整除9题，数据都指向今年（2026）这类题可能继续以“筛数+验证”的组合形式出现，比如换个更大的n或者加个随机测试。暂无足够依据预测具体年份的考题，但可以肯定的是，只要涉及质数筛和哥德巴赫猜想验证，思路主线不变：先筛后验，细节决定生死。