1. 题目分析与解题思路
素数（质数）是指大于1的自然数中，除了1和它本身外，没有其他因数的数。这道题目要求我们统计给定区间[A,B]内所有素数的个数。作为C++编程的经典题目，它不仅考察了对素数的理解，还检验了循环结构和枚举法的应用能力。
1.1 素数判断的基本方法
判断一个数是否为素数，主要有两种基本思路：
- 因数计数法：统计一个数的因数个数，如果恰好有2个因数（1和它本身），则为素数。
- 标记法：假设一个数是素数，然后检查是否存在能整除它的数（除了1和它本身），如果存在则标记为非素数。
这两种方法各有优劣，因数计数法直观但效率较低，标记法效率稍高但需要额外变量存储标记状态。
1.2 算法效率分析
对于区间[A,B]中的每个数i，我们需要判断它是否为素数。最直观的方法是：
- 对于每个i，检查2到i-1的所有数是否能整除i
- 如果没有任何数能整除i，则i是素数
这种方法的时间复杂度是O(n²)，当n较大时（比如n=10⁶），效率会非常低。因此在实际应用中，我们通常会使用更高效的算法，如埃拉托斯特尼筛法（筛法）。但作为基础练习，我们先掌握这两种基本方法。
2. 解法1：因数计数法实现
2.1 代码实现详解
cpp复制#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B; // 输入区间范围
int cnt = 0; // 素数计数器
for(int i = A; i <= B; i++) { // 遍历区间内每个数
int p = 0; // 因数计数器
for(int j = 1; j <= i; j++) { // 检查1到i的所有数
if(i % j == 0) { // 如果j是i的因数
p++; // 因数个数加1
}
}
if(p == 2) { // 如果因数个数正好是2
cnt++; // 则是素数，计数器加1
}
}
cout << cnt; // 输出素数个数
return 0;
}
2.2 关键点解析
- 双重循环结构：外层循环遍历区间内每个数，内层循环检查每个数的因数。
- 因数计数：内层循环中，每当发现一个因数，就将计数器p加1。
- 素数判断：循环结束后，如果p的值为2，说明这个数只有1和它本身两个因数，是素数。
2.3 优化空间
这个解法虽然直观，但效率不高。我们可以做以下优化：
- 减少检查范围：实际上，只需要检查2到√i的数即可，因为如果i有大于√i的因数，那么它必然有一个小于√i的对应因数。
- 提前终止：一旦发现超过2个因数，就可以立即终止内层循环，因为已经确定不是素数了。
3. 解法2：标记法实现
3.1 代码实现详解
cpp复制#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B; // 输入区间范围
int cnt = 0; // 素数计数器
for(int i = A; i <= B; i++) { // 遍历区间内每个数
int isPrime = 1; // 初始假设是素数
for(int j = 2; j < i; j++) { // 检查2到i-1的所有数
if(i % j == 0) { // 如果j能整除i
isPrime = 0; // 标记为非素数
break; // 可以提前终止内层循环
}
}
if(isPrime && i > 1) { // 注意排除1的特殊情况
cnt++; // 素数计数器加1
}
}
cout << cnt; // 输出素数个数
return 0;
}
3.2 关键点解析
- 标记变量：使用isPrime作为标记，初始假设当前数是素数。
- 提前终止：一旦发现能整除的数，立即标记为非素数并终止内层循环。
- 特殊处理1：1不是素数，需要额外判断i>1。
3.3 优化建议
- 缩小检查范围：同样可以只检查2到√i的数。
- 跳过偶数：除了2，所有偶数都不是素数，可以特殊处理。
- 预先生成素数表：对于多次查询的情况，可以预先生成素数表。
4. 性能对比与选择建议
4.1 时间复杂度分析
两种解法在最坏情况下都是O(n²)时间复杂度，但实际运行中：
- 因数计数法必须完整遍历所有可能的因数
- 标记法可以在发现非素数时提前终止
因此标记法在实际运行中通常更快。
4.2 内存使用
两种解法都只需要常数级别的额外空间，内存使用差异不大。
4.3 适用场景选择
- 小范围区间（如B<10⁵）：两种方法都可以
- 大范围区间（如B≥10⁶）：建议使用更高效的筛法
- 教学目的：因数计数法更直观易懂
- 竞赛场景：标记法效率更高
5. 常见问题与调试技巧
5.1 边界条件处理
- 区间端点：确保正确处理A和B的边界值
- 数字1：1不是素数，需要特殊处理
- 负数和零：题目通常保证A≥1，但实际应用中需要考虑
5.2 常见错误
- 忘记初始化计数器：导致统计结果错误
- 内层循环范围错误：如j从0开始，会导致除以0错误
- 标记变量使用不当：在标记法中忘记重置isPrime
5.3 调试建议
- 打印中间结果：对于小范围输入，打印每个数的判断过程
- 使用已知结果验证：如1-10的素数个数应为4个
- 性能测试：对于大输入，测试程序运行时间
6. 算法优化进阶
6.1 平方根优化
判断素数时，只需要检查2到√i的数：
cpp复制for(int j = 2; j * j <= i; j++) {
if(i % j == 0) {
isPrime = 0;
break;
}
}
这种优化可以将时间复杂度降低到O(n√n)。
6.2 筛法实现
埃拉托斯特尼筛法是一种更高效的素数查找算法，适合处理大范围素数统计：
cpp复制#include <iostream>
#include <vector>
using namespace std;
int countPrimes(int A, int B) {
if(B < 2) return 0;
vector<bool> isPrime(B+1, true);
isPrime[0] = isPrime[1] = false;
for(int i = 2; i * i <= B; i++) {
if(isPrime[i]) {
for(int j = i * i; j <= B; j += i) {
isPrime[j] = false;
}
}
}
int cnt = 0;
for(int i = A; i <= B; i++) {
if(isPrime[i]) cnt++;
}
return cnt;
}
int main() {
int A, B;
cin >> A >> B;
cout << countPrimes(A, B);
return 0;
}
筛法的时间复杂度是O(n log log n)，适合处理B≤10⁷的情况。
6.3 其他优化技巧
- 只检查奇数：除了2，所有素数都是奇数
- 预生成小素数：先生成小素数列表，只检查这些素数的倍数
- 分段筛法：处理极大范围时，可以分段进行筛法
7. 实际应用与扩展
素数判断在密码学、哈希算法等领域有广泛应用。理解这些基础算法有助于：
- RSA加密算法：基于大素数的难分解性
- 哈希函数设计：使用素数减少冲突
- 算法竞赛：是许多高级算法的基础
在实际编程中，我们通常会：
- 预计算素数表：对于需要频繁查询的场景
- 使用概率性测试：如Miller-Rabin测试，处理极大数
- 利用数学库：如C++的GMP库提供高效素数测试
对于初学者来说，掌握这两种基础方法非常重要，它们是理解更高级算法的基础。在实际编程练习中，建议从简单方法开始，逐步尝试优化和更高效的算法。