【GESP】C++二级真题 luogu-P1304 哥德巴赫猜想

GESP二级真题，多层循环和分支练习，难度★★☆☆☆。

luogu-P1304 哥德巴赫猜想

题目要求

题目描述

输入一个偶数 $N$，验证 $4\sim N$ 所有偶数是否符合哥德巴赫猜想：任一大于 $2$ 的偶数都可写成两个质数之和。如果一个数不止一种分法，则输出第一个加数相比其他分法最小的方案。例如 $10$，$10=3+7=5+5$，则 $10=5+5$ 是错误答案。

输入格式

第一行输入一个正偶数 $N$

输出格式

输出 $\dfrac{N-2}{2}$ 行。对于第 $i$ 行：

首先先输出正偶数 $2i+2$，然后输出等号，再输出加和为 $2i+2$ 且第一个加数最小的两个质数，以加号隔开。

输入 #1

10

输出 #1

4=2+2
6=3+3
8=3+5
10=3+7

说明/提示

数据保证，$ 4 \leq N\leq10000$。

---

题目分析

解题思路

1. 读取输入的正偶数N。
2. 从4开始，到N结束，每次增加2，遍历所有偶数。
3. 对于每个偶数i，初始化变量other为0，用于存储i减去j的结果。
4. 从2开始，到i的一半结束，遍历所有可能的j。
5. 计算i减去j的结果，并存储在other中。
6. 检查j是否为质数，如果不是，则继续下一轮循环。
7. 如果j是质数，则检查other是否为质数。
8. 如果j和other都是质数，则输出结果，格式为i=j+other，并跳出循环。
9. 重复步骤3-8，直到遍历完所有偶数。

—·

示例代码

#include <cmath>
#include <iostream>

using namespace std;
int main() {
    int n; // 读取输入的正偶数N
    cin >> n; // 从输入流中读取N的值
    for (int i = 4; i <= n; i += 2) { // 从4开始，到N结束，每次增加2
        int other = 0; // 初始化变量other，用于存储i减去j的结果
        for (int j = 2; j <= i / 2; j++) { // 从2开始，到i的一半结束
            bool flag = true; // 初始化标志位，用于判断j和other是否为质数
            other = i - j; // 计算i减去j的结果
            for (int k = 2; k <= sqrt(j); k++) { // 从2开始，到j的平方根结束
                if (j % k == 0) { // 如果j能被k整除，则j不是质数
                    flag = false; // 将标志位设置为false
                    break; // 跳出循环
                }
            }
            if (!flag) { // 如果j不是质数，则继续下一轮循环
                continue;
            } else { // 如果j是质数，则检查other是否为质数
                for (int k = 2; k <= sqrt(other); k++) { // 从2开始，到other的平方根结束
                    if (other % k == 0) { // 如果other能被k整除，则other不是质数
                        flag = false; // 将标志位设置为false
                        break; // 跳出循环
                    }
                }
            }
            if (flag) { // 如果j和other都是质数，则输出结果
                cout << i << "=" << j << "+" << other << endl; // 输出格式为i=j+other
                break; // 跳出循环
            }
        }
    }
    return 0; // 程序返回0，表示执行成功
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。