2026-09 · 5级 · 哥德巴赫猜想

GESP 标程 · 考级真题 · 代码 · cpp · 难度 5/5 · 共 866 字

CCF 原卷官方标程 · 质数、组合数学 · 本地编译通过

2026-09
质数

正文

// GESP 2026-09 C++ 5级 编程题 1 · 哥德巴赫猜想
// 原题：https://oj.yecheng.tv/p/gs2609l5p1
// 官方原卷：https://gesp.ccf.org.cn/101/attach/1767258833551392.pdf
// 题意：众所周知，哥德巴赫猜想是说，任何大于的偶数都能写成两个质数(素数)之和。
// 知识点：质数、组合数学
// 参考程序：CCF 原卷官方标程，PDF 抽取后已去行号；本地编译核验通过，供打字练习
// 原卷样例验证：样例验证 2/2 通过
//
#include <cassert>
#include <cstdio>
using namespace std;
int n, ans;
bool not_prime[1000005];
int primes[500000], pcnt = 0;
void get_primes() {
    not_prime[1] = true;
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            primes[pcnt++] = i;
            for (int j = 2; i * j <= n; ++j) {
                not_prime[i * j] = true;
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    get_primes();
    for (int i = 0; i < pcnt && primes[i] <= n / 2; ++i)
        if (!not_prime[n - primes[i]])
            ans++;
    printf("%d\n", ans);
    return 0;
}

2026-09 · 5级 · 哥德巴赫猜想

正文

GESP 标程 · 考级真题的其它内容