NOIP 普及 2010 第一轮 第 31 题：哥德巴赫猜想验证：第 5 空

题目

完善程序：
（哥德巴赫猜想）哥德巴赫猜想是指，任一大于 $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<<ans<<endl;
    return 0;
}

若输入 $n$ 为 $2010$，则输出[    ⑤   ]时表示验证成功，即大于 $2$ 且不超过 $2010$ 的偶数都满足哥德巴赫猜想。

⑤处应填（ ）

答案

1004

题解

考点定位

本题（哥德巴赫第⑤空）考「验证成功的输出值」,对应大纲 3.3.4 枚举（难度【3】）。

解题过程

ans 计「能写成两素数之和的偶数」个数。n=2010 时小于等于 2010 的偶数（>2）共 (2010−2)/2 = 1004 个。验证成功 ⟺ ans=1004。

答案：1004。

易错提醒

① 偶数从 4 到 2010：个数 = (2010−4)/2+1 = 1004；② 「验证成功」的输出 = 全部偶数个数。