编程求助：计算L-R范围内平方根为质数的完全平方数个数

你的问题其实可以转化为更简单的形式：满足条件的数本质上是「质数的平方」——因为条件要求数是完全平方数（即形如p²），且平方根p是质数。所以问题等价于：统计区间 [ceil(√L), floor(√R)] 内的质数个数，这个个数就是你要的答案。

为什么你的原解法会超时？ #

你原来的思路是遍历区间内的每个完全平方数，再通过哈希表判断其平方根是否为质数。但当R达到1e12时，区间内的完全平方数最多有1e6个（因为√1e12=1e6），如果T=1e4，总操作次数会达到1e10次，远远超过1秒能处理的上限（通常1秒约能处理1e8次操作），必然会触发TLE。

优化方案：预处理+O(1)查询 #

我们可以提前预处理出所有可能的质数（因为p最大是1e6，p²才会≤1e12），再用前缀和数组快速统计区间内的质数个数，具体步骤如下：

1. 预处理阶段

• 埃氏筛生成质数标记：用筛法找出1到1e6之间的所有质数，存入is_prime数组（is_prime[p]为true表示p是质数）。
• 前缀和数组：构建prefix数组，其中prefix[x]表示1到x之间的质数总数。这样后续查询区间[a,b]的质数个数时，直接用prefix[b] - prefix[a-1]即可。

2. 查询阶段

对每组测试用例：

• 计算low = ceil(√L)（即最小的p使得p²≥L）
• 计算high = floor(√R)（即最大的p使得p²≤R）
• 如果low > high，说明区间内没有符合条件的数，答案为0；否则用前缀和数组计算[low, high]内的质数个数，就是最终答案。

代码示例（C++） #

#include <iostream>
#include <vector>
using namespace std;

const int MAX_PRIME = 1e6;
vector<bool> is_prime(MAX_PRIME + 1, true);
vector<int> prime_count_prefix(MAX_PRIME + 1, 0);

void precompute() {
    // 埃氏筛初始化
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_PRIME; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= MAX_PRIME; j += i) {
                is_prime[j] = false;
            }
        }
    }
    // 构建前缀和数组
    for (int i = 1; i <= MAX_PRIME; ++i) {
        prime_count_prefix[i] = prime_count_prefix[i-1] + (is_prime[i] ? 1 : 0);
    }
}

// 二分法计算ceil(sqrt(x))，避免浮点精度问题
long long ceil_sqrt(long long x) {
    if (x == 0) return 0;
    long long left = 1, right = MAX_PRIME;
    long long ans = right;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if ((long long)mid * mid >= x) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

// 二分法计算floor(sqrt(x))
long long floor_sqrt(long long x) {
    long long left = 1, right = MAX_PRIME;
    long long ans = 0;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if ((long long)mid * mid <= x) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

int main() {
    // 加速输入输出，应对T=1e4的情况
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    precompute();
    
    int T;
    cin >> T;
    while (T--) {
        long long L, R;
        cin >> L >> R;
        
        long long lower = ceil_sqrt(L);
        long long upper = floor_sqrt(R);
        
        if (lower > upper) {
            cout << "0\n";
            continue;
        }
        
        // 因为upper <= 1e6，直接转int安全
        int result = prime_count_prefix[(int)upper] - prime_count_prefix[(int)lower - 1];
        cout << result << "\n";
    }
    return 0;
}

关键细节说明 #

• 避免浮点误差：用二分法计算平方根，而不是直接调用sqrt()函数，防止因为浮点精度问题导致的错误（比如当x是接近完全平方数的大数时，sqrt(x)的整数转换可能出错）。
• 输入输出加速：用ios::sync_with_stdio(false);和cin.tie(nullptr);关闭同步，大幅提升cin/cout的速度，应对1e4组测试用例的输入需求。
• 时间复杂度：预处理阶段是O(n log log n)（n=1e6），查询阶段每组是O(1)，总时间完全符合1秒的限制。

内容的提问来源于stack exchange，提问作者Lucosa