本文共 2034 字，大约阅读时间需要 6 分钟。
最近，我遇到了一个编程题，题目是关于区间内质数的个数统计。这个题目看起来不复杂，但实际上却隐藏了一些需要注意的地方。题目名称虽然吸引人，但实际内容却相当实用。
题目要求，对于给定的多个区间 [l, r]，统计每个区间内质数的个数。需要注意的是，输入的 l 或 r 有可能超出给定的范围 [1, m]，这种情况下应该输出 "Crossing the line"。
n 和 m，分别表示询问次数和范围上限。n 行，每行包含两个整数 l 和 r，表示区间。l 或 r 超出范围 [1, m]，则输出 "Crossing the line"。输入样例#1：
2 51 32 651 326 32
输出样例#1：
Crossing the line2
这个问题看似简单，但要实现高效的解决方案，需要注意以下几点：
m 较大时，这种方法会非常低效。O(1) 时间内查询区间内质数的个数。l 和 r 进行有效性检查，确保它们在合理范围内。质数的分布具有某种规律性，可以利用贪心算法结合筛选法来预处理质数。具体来说：
f，其中 f[i] 表示 i 是否为质数。0，质数则标记为 1。f，其中 f[i] 表示从 1 到 i 的质数个数。这样可以快速计算任意区间 [l, r] 内质数的个数。#include#include #include #include #include using namespace std;bool judge(int x) { if (x <= 1) return false; for (int i = 2; i * i <= x; ++i) { if (x % i == 0) return false; } return true;}int main() { scanf("%d%d", &n, &m); int f[m + 1]; for (int i = 1; i <= m; ++i) { if (judge(i)) { f[i] = f[i - 1] + 1; } else { f[i] = f[i - 1]; } } for (int i = 1; i <= n; ++i) { int l, r; scanf("%d%d", &l, &r); if (l < 1 || l > m || r < 1 || r > m) { printf("Crossing the line\n"); } else { int count = f[r] - f[l - 1]; printf("%d\n", count); } } return 0;}
judge(int x) 函数用于判断一个数是否为质数。通过试除法，从 2 到 sqrt(x) 检查是否有因数。main 函数中，首先读取输入参数 n 和 m。然后初始化一个数组 f，用于记录每个数是否为质数。1 到 m 的每个数，使用 judge 函数判断是否为质数，并根据结果更新前缀和数组 f。l 和 r，并检查它们是否在有效范围内。如果超出范围，输出 "Crossing the line"；否则，通过前缀和数组快速计算区间内的质数个数并输出。m，使用筛选法预处理质数是高效的选择。避免在查询时逐个判断每个数是否为质数，这会导致超时。judge 简化，直接在预处理阶段完成质数标记，这样可以提高处理速度。通过以上方法，可以高效地解决区间质数个数的问题，确保在大数据范围内也能快速响应。
转载地址：http://xdvfk.baihongyu.com/