PAT乙级1007

常规解法

#include <iostream>
using namespace std;// 判断一个数是否为素数的函数
bool isprime(int a) {// 遍历 2 到 sqrt(a) 之间的数，判断 a 是否能被它们整除for (int i = 2; i * i <= a; i++) {if (a % i == 0)  // 如果能整除，说明 a 不是素数return false;}return true;  // 如果没有找到能整除的数，说明 a 是素数
}int main() {int N, cnt = 0;  // N 为输入的数字，cnt 用于统计符合条件的素数对数量cin >> N;  // 输入一个正整数 N// 从 5 开始遍历到 N，因为素数对的第一位素数必须从 5 开始// 对于每一个 i，检查 i 和 i-2 是否为素数for (int i = 5; i <= N; i++) {// 检查 i 和 i-2 是否都是素数if (isprime(i - 2) && isprime(i)) {cnt++;  // 如果是素数对，增加计数}}cout << cnt;  // 输出符合条件的素数对的数量return 0;
}

代码解析：
1. isprime(int a)：
这是一个判断一个数是否为素数的函数。它通过遍历从 2 到 sqrt(a) 的整数，检查 a 是否能被这些数整除。如果能整除，返回 false，说明 a 不是素数；如果不能整除，返回 true，说明 a 是素数。
2. main()：
• 读取输入的整数 N，表示我们要检查的素数范围。
• 变量 cnt 用来统计符合“差为 2 的素数对”的个数。
• 从 5 开始遍历直到 N，因为我们只关心从 5 开始的素数对（即差为 2 的素数对的第一个素数从 5 开始）。
• 对于每个 i，检查 i 和 i-2 是否都是素数，如果是，说明它们是一个符合条件的素数对，增加计数 cnt。
• 最后输出符合条件的素数对的数量。

示例：

输入：

20

输出：

4

解释：
• 在小于等于 20 的素数中，存在以下符合条件的素数对：
• (5, 7)
• (11, 13)
• (17, 19)
• 总共 3 对符合条件，因此输出结果是 3。

优化建议：
• 时间复杂度： isprime 函数的时间复杂度是 O(sqrt(a))，所以整体代码的时间复杂度是 O(N * sqrt(N))，这对于最大 N = 100000 可能有一定的性能瓶颈。为了进一步提高性能，可以考虑使用埃拉托斯特尼筛法来预先计算素数。

素数筛选法

埃拉托斯特尼筛法（Sieve of Eratosthenes） 是一种用于计算某个范围内所有素数的高效算法。它由古希腊数学家埃拉托斯特尼提出，主要通过标记非素数来逐步筛选出素数。这个方法非常适用于寻找小范围内的所有素数，时间复杂度为 O(n log log n)，其中 n 是上限。

埃拉托斯特尼筛法的基本思想：
1. 假设我们需要找出 1 到 n 之间的所有素数。
2. 首先假设所有的数字都是素数，将所有数字标记为“可能是素数”。
3. 从 2 开始，检查每个数字：
• 如果该数字被标记为素数，则从它的平方开始，将它的所有倍数标记为“非素数”。
• 继续处理下一个未标记的数字，直到所有数字处理完成。
4. 剩下标记为“素数”的数字即为所有素数。

具体步骤：
1. 创建一个布尔数组 is_prime，数组大小为 n+1，并将所有元素初始化为 true（表示所有数字都是素数）。
2. 标记 is_prime[0] 和 is_prime[1] 为 false，因为 0 和 1 不是素数。
3. 从 2 开始，检查每个数字：
• 如果 is_prime[i] 为 true，则从 i * i 开始标记 i 的所有倍数为非素数。
• 重复这个过程，直到 i * i > n。
4. 最后，所有 is_prime[i] 为 true 的位置 i 对应的数字就是素数。

示例：寻找小于等于 20 的所有素数

步骤：
1. 初始化布尔数组 is_prime[0…20]：

is_prime[0…20] = {false, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true}

2.	从 2 开始，处理数字 2：
•	标记 2 的倍数：4, 6, 8, 10, 12, 14, 16, 18, 20 为非素数。
•	更新 is_prime 数组：

is_prime[0…20] = {false, false, true, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false, true, false}

3.	处理下一个未被标记的数字 3：
•	标记 3 的倍数：9, 12, 15, 18 为非素数。
•	更新 is_prime 数组：

is_prime[0…20] = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, true, false, true, false, true, false}

4.	继续处理 5、7 等，直到所有数字处理完。

最终，is_prime 数组中标记为 true 的位置对应的数字是素数：

2, 3, 5, 7, 11, 13, 17, 19

C++ 实现：

#include
#include
using namespace std;

void sieve_of_eratosthenes(int n) {
// 创建一个布尔数组，初始化为 true，表示所有数都是素数
vector is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数

// 从 2 开始，筛选出所有的素数
for (int i = 2; i * i <= n; i++) {if (is_prime[i]) {  // 如果 i 是素数for (int j = i * i; j <= n; j += i) {is_prime[j] = false; // 将 i 的倍数标记为非素数}}
}// 输出所有素数
for (int i = 2; i <= n; i++) {if (is_prime[i]) {cout << i << " ";}
}
cout << endl;

}

int main() {
int N;
cin >> N;
sieve_of_eratosthenes(N); // 输出不超过 N 的所有素数
return 0;
}

代码解释：
1. 布尔数组 is_prime： 用来标记数字是否是素数，初始化时将所有数字标记为 true。
2. 筛选过程： 从 2 开始，如果某个数是素数，则标记它的倍数为 false，直到 i * i > n。
3. 输出素数： 在所有数字处理完后，输出 is_prime 数组中标记为 true 的数字。

优点：
• 高效性： 埃拉托斯特尼筛法的时间复杂度为 O(n log log n)，比简单的逐个检查每个数字是否为素数要高效得多。
• 适用于较大的 n： 即使对于较大的 n，这个算法仍然能在合理的时间内找到所有素数。

复杂度：
• 时间复杂度： O(n log log n)，对于 n 范围内的素数查找非常高效。
• 空间复杂度： O(n)，用于存储 is_prime 数组。