【入门篇】哥德巴赫猜想—

# [NOIP2004 提高组] 津津的储蓄计划

题目描述

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津 $300$ 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 $20\%$ 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 $100$ 元或恰好 $100$ 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如 $11$ 月初津津手中还有 $83$ 元，妈妈给了津津 $300$ 元。津津预计 $11$ 月的花销是 $180$ 元，那么她就会在妈妈那里存 $200$ 元，自己留下 $183$ 元。到了 $11$ 月月末，津津手中会剩下 $3$ 元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据 $2004$ 年 $1$ 月到 $12$ 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 $2004$ 年年末，妈妈将津津平常存的钱加上 $20\%$ 还给津津之后，津津手中会有多少钱。

输入格式

$12$ 行数据，每行包含一个小于 $350$ 的非负整数，分别表示 $1$ 月到 $12$ 月津津的预算。

输出格式

一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出 $- X$ ， $X$ 表示出现这种情况的第一个月；否则输出到 $2004$ 年年末津津手中会有多少钱。

注意，洛谷不需要进行文件输入输出，而是标准输入输出。

样例 #1

样例输入 #1

样例输出 #1

-7

样例 #2

样例输入 #2

样例输出 #2

这道 哥德巴赫猜想 的题目，我们需要为每一个小于或等于 N 的偶数 2i + 2 找出两数之和，其中这两个数是质数，并且保证第一个加数是最小的。这是一个典型的质数分解问题。

题目分析：

输入格式：
- 输入一个正偶数 N，表示要验证的最大偶数。
输出格式：
- 对于每个偶数 4 <= 2i+2 <= N，输出它最小的质数加法表示。即对于每个偶数 2i+2，我们要找两个质数 p1 和 p2，使得 p1 + p2 = 2i + 2，且 p1 是第一个出现的质数。
- 如果一个偶数可以有多种表示方式，则输出第一个加数最小的表示。

解题思路：

判断质数：
- 我们需要判断哪些数是质数。在这里，我们可以使用 埃拉托斯特尼筛法 来求出所有小于或等于 N 的质数。这个方法高效，可以帮助我们快速筛选出所有质数。
枚举偶数：
- 对于每一个偶数 2i + 2，我们需要找到一对质数 p1 和 p2，使得 p1 + p2 = 2i + 2。
- 由于题目要求第一个加数最小，因此我们可以从 2 开始，遍历所有小于等于 2i+2 的质数，判断 p2 = 2i+2 - p1 是否是质数。
优化：
- 我们可以使用一个布尔数组 isPrime[]，记录每个数字是否为质数，这样可以避免重复计算质数。
- 对于每个偶数 2i + 2，我们可以从 2 开始遍历质数，找到第一个符合条件的质数对。
输出：
- 输出格式严格要求每行输出一个偶数，后面跟着等式和两个质数。

埃拉托斯特尼筛法（Sieve of Eratosthenes） 是一个用于寻找所有小于等于某个正整数 n 的质数的经典算法。其核心思想是利用已知质数的倍数不是质数，通过不断筛选，最终得到所有质数。

埃拉托斯特尼筛法的原理：

初始化：从 2 开始，假设所有数都可能是质数。创建一个布尔数组 isPrime[]，其中 isPrime[i] 表示数 i 是否是质数。初始化所有元素为 True，表示所有数都是质数（除了 0 和 1 ）。isPrime[0] 和 isPrime[1] 设置为 False，因为 0 和 1 不是质数。
筛选过程：从 2 开始，遍历每一个数 i，如果 i 是质数（isPrime[i] == True），则将 i 的所有倍数（即 2i, 3i, 4i, ...）标记为非质数（isPrime[k] = False）。
结束条件：当 i 的平方大于 n 时，筛选过程结束。因为如果一个合成数 k 大于 sqrt(n)，那么它必定可以被某个较小的质数整除，这些较小的质数早已被筛选掉。
输出结果：筛选结束后，所有 isPrime[i] == True 的 i 即为质数。

埃拉托斯特尼筛法的步骤和伪代码：

步骤：

创建布尔数组 isPrime[]：初始化所有数字为 True，但 isPrime[0] 和 isPrime[1] 设置为 False。
遍历每个数字 i：
- 如果 i 是质数（即 isPrime[i] == True），则从 i^2 开始，标记所有 i 的倍数为非质数。
- 继续遍历直到 i^2 > n。
输出：筛选完成后，isPrime[] 中值为 True 的索引就是质数。

伪代码：

function sieveOfEratosthenes(n):1. 创建一个布尔数组 isPrime[n + 1]，并初始化为 True2. 设置 isPrime[0] = isPrime[1] = False3. 从 2 开始遍历到 √n：4. 如果 isPrime[i] 是 True：5. 对于 i 的每个倍数 j（从 i^2 开始，步长为 i）：6. 设置 isPrime[j] = False7. 输出所有 isPrime[i] == True 的索引 i

该方法的应用场景：

质数测试：可以在处理大规模数据时用筛法预处理质数，快速判断一个数是否为质数。
大数分解：如果要做因数分解，筛法可以帮助快速找到小于某个数的质数。
求质数和：例如在数论中，很多问题都需要用到质数的性质，可以使用筛法提前准备质数集合，提升算法效率。

代码实现：

Java 代码：

java">import java.util.Scanner;public class GoldbachConjecture {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();// 1. 筛选出所有小于等于 N 的质数boolean[] isPrime = new boolean[N + 1];for (int i = 2; i <= N; i++) {isPrime[i] = true;}for (int i = 2; i * i <= N; i++) {if (isPrime[i]) {for (int j = i * i; j <= N; j += i) {isPrime[j] = false;}}}// 2. 对每个偶数 4 到 N，找到符合条件的质数分解for (int i = 2; i <= N / 2; i++) {int even = 2 * i;for (int j = 2; j <= even / 2; j++) {if (isPrime[j] && isPrime[even - j]) {System.out.println(even + "=" + j + "+" + (even - j));break;}}}}
}

C 代码：

#include <stdio.h>
#include <stdbool.h>int main() {int N;scanf("%d", &N);// 1. 筛选出所有小于等于 N 的质数bool isPrime[N + 1];for (int i = 2; i <= N; i++) {isPrime[i] = true;}for (int i = 2; i * i <= N; i++) {if (isPrime[i]) {for (int j = i * i; j <= N; j += i) {isPrime[j] = false;}}}// 2. 对每个偶数 4 到 N，找到符合条件的质数分解for (int even = 4; even <= N; even += 2) {for (int j = 2; j <= even / 2; j++) {if (isPrime[j] && isPrime[even - j]) {printf("%d=%d+%d\n", even, j, even - j);break;}}}return 0;
}

C++ 代码：

#include <iostream>
#include <vector>using namespace std;int main() {int N;cin >> N;// 1. 筛选出所有小于等于 N 的质数vector<bool> isPrime(N + 1, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i * i <= N; i++) {if (isPrime[i]) {for (int j = i * i; j <= N; j += i) {isPrime[j] = false;}}}// 2. 对每个偶数 4 到 N，找到符合条件的质数分解for (int even = 4; even <= N; even += 2) {for (int j = 2; j <= even / 2; j++) {if (isPrime[j] && isPrime[even - j]) {cout << even << "=" << j << "+" << (even - j) << endl;break;}}}return 0;
}

Python 代码：

python">def main():N = int(input())# 1. 筛选出所有小于等于 N 的质数is_prime = [True] * (N + 1)is_prime[0] = is_prime[1] = Falsefor i in range(2, int(N**0.5) + 1):if is_prime[i]:for j in range(i * i, N + 1, i):is_prime[j] = False# 2. 对每个偶数 4 到 N，找到符合条件的质数分解for even in range(4, N + 1, 2):for j in range(2, even // 2 + 1):if is_prime[j] and is_prime[even - j]:print(f"{even}={j}+{even - j}")breakif __name__ == "__main__":main()

代码解释：

质数筛选：
- 使用布尔数组 isPrime[] 来标记每个数是否是质数。
- 通过埃拉托斯特尼筛法，从小到大标记质数。每个质数的倍数都标记为非质数。
处理偶数：
- 对每个偶数 2i + 2，遍历 2 到 2i + 2 中的所有质数，找到第一个符合条件的质数对。
输出：
- 对每个偶数输出结果，格式为 偶数=质数1+质数2。

时间复杂度：

埃拉托斯特尼筛法的时间复杂度为 O(N log log N)，用来筛选质数。
对于每个偶数 2i+2，最多遍历其一半的质数，复杂度为 O(N^2)。

因此，整体复杂度大约是 O(N^2)，对于 N 最大为 10000，计算量是可以接受的。

补充：

在埃拉托斯特尼筛法中，当我们筛选质数时，只需要检查到 sqrt(n) 为止，原因在于一个合成数总是可以分解为两个因子，其中至少一个因子不大于 sqrt(n)。

分析：

假设你要判断一个数 k 是否是质数。如果 k 不是质数，那么它可以分解为两个因子 a 和 b，使得 k = a * b。根据乘法性质，如果 a 和 b 都大于 sqrt(k)，那么它们的乘积 a * b 必然大于 k，这与 k 的定义矛盾。所以，至少有一个因子 a 必须小于或等于 sqrt(k)。

因此，当我们筛选质数时，只需要检查 2 到 sqrt(n) 范围内的数，因为大于 sqrt(n) 的因子，必定有一个小于 sqrt(n)，而这些小于 sqrt(n) 的数已经被筛掉了。这样就能确保所有合成数都被标记为非质数。

举个例子：

假设我们要找小于等于 100 的质数。根据这个原理，我们只需要检查 2 到 sqrt(100)，也就是 2 到 10 的数：

如果某个数 k 是合成数，它必定可以被 2, 3, 5, 7 这些小于 10 的质数整除。
因此，只需要标记 2 到 10 的倍数，超过 10 的合成数会在筛选过程中被已标记的质数因子筛除。

常见错误：

1. 质数判断错误

问题：错误地判断质数，比如认为 1 是质数，或者在检查质数时忽略了某些优化。
解决方法：使用 埃拉托斯特尼筛法 生成质数数组，这是高效且常用的方法，避免重复计算。质数的定义是大于 1 的整数，且只能被 1 和它本身整除。

2. 误处理输入边界

问题：输入的偶数 N 是最小值 4，或者非常接近最大值 10000 时，容易在循环或数组操作时出现越界错误。
解决方法：确保输入范围符合题意（4 <= N <= 10000），并且在对数组操作时要特别注意下标范围。

3. 找最小的质数对时顺序错误

问题：如果输出的质数对顺序错误，比如未能保证第一个加数最小，会导致结果不符合题目要求。
解决方法：在遍历每个偶数时，保证 p1 是从小到大检查质数，找到的第一个符合 p1 + p2 = 2i + 2 的对即为解。

4. 数组或循环错误

问题：由于需要检查每个偶数 2i + 2，有时可能在查找合适的质数对时，忘记了 2i + 2 的范围，或者错误地处理了数组的长度，导致超出有效范围。
解决方法：在进行质数对的查找时，需要确认 p2 = 2i + 2 - p1 也是一个质数，并且确保 p1 小于或等于 p2。

5. 输出格式错误

问题：输出格式不符合要求，如没有按照 2i + 2= p1 + p2 的格式输出，或者遗漏了等号、加号等符号。
解决方法：按照题目要求，输出的格式要严格遵守，每行的格式要是 x = p1 + p2，并且输出的顺序要与偶数递增一致。

6. 性能问题

问题：如果使用简单的质数检查方法（如每次检查一个数是否能整除所有小于它的数），对于较大的 N，可能会导致时间超限。
解决方法：使用 埃拉托斯特尼筛法 预处理所有小于等于 N 的质数，这样可以提高性能，避免在每次求解时都进行重复的质数判断。

7. 忽略边界条件

问题：有些情况下忽略了对 N 较小值的特别处理，比如 N=4 时，输出应该是 4=2+2，没有做特别处理会导致错误。
解决方法：特别注意边界值的处理，确保 N 的最小值（如 4）和其他极限条件时的输出结果正确。

8. 内存/空间限制

问题：在处理大范围的数据时，可能因为使用了过多的内存（例如在存储质数时），导致空间超出限制。
解决方法：对于质数的存储，可以使用布尔数组表示质数的真假，节省内存。

总结：

确保质数筛选正确、输出格式符合要求、避免越界、性能优化是解决这道题的关键。埃拉托斯特尼筛法 是一个常见且高效的方法，能够避免重复判断质数并提高效率。