找出多少个正整数，并且sqrt（）是L，R范围内的质数

Question

首先，请随时改进问题的格式

[Goswin von Brederlow已经解决了这个问题！

你好，我正在编程，遇到了这个问题，我不知道解决这个问题的最佳方法是什么：

问题有T个测试用例，其中包括：

给定范围L和R，找出有多少个数字满足约束：

i）数字是一个完美的正方形；

ii）sqrt（Number）是质数。

限制：

1 <= T <= 1e4

1 <= L，R <= 1e12

时间限制：1秒

所以，我尝试了一个简单的想法，即使用unodered_map（lld，bool）对每个sqrt（Number）进行筛选，并使用eratosthenes筛子进行筛选，因为Number是一个完美的正方形

[之后，我传入范围pow（sqrt（l），2）并将其递增下一个奇数...，例如：4 9 16 25，差是奇数：5 7 9 ...

我的代码：

long long int l, r; scanf("%lld %lld", &l, &r);
long long int odd = ceil(sqrt(l)), n = odd*odd;
odd = (2*odd) + 1;
long long int ans = 0;
while((n >= l && n <= r)){
    it = h.find(n);
    ans = ans + it->second;
    n = n + odd; 
    odd = odd + 2;
}

但是我仍然获得TLE，我需要一些帮助，谢谢！

Answer 1

我看到的唯一问题是“我不知道如何解决此问题的最佳方法”。

您的方式似乎已经很聪明了。即使只是粘贴一些代码，您仍然会有一些错误。您似乎是在计算数字的总和，而不是对它们进行计数。

我想改进的一件事就是计数本身。看起来您有一个包含所有素数平方的哈希表，并且只需测试所有auqares是否在表中即可。

为什么不从素数中制成一棵平衡的树？在每个节点中，存储子树的最小和最大数目以及计数。叶子将是（n，n，1），其中n是素数的平方之一。给定L和R，您便可以遍历该树，对区间中的所有子树求和，然后递归为仅部分位于内部的子树。忽略外面的一切。这应该为您的复杂性增加一个对数因子。

Answer 2

所有数字的形式为p ^ 2，具有p质数，并且p <= 10 ^ 6（因为p ^ 2 <= 10 ^ 12）。使用Eratosthenes筛（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）来计算所有这样的质数（这是计算质数的一种非常常见的方法）。存储所有这些素数后，可以执行二进制搜索以查看其中有多少个素数的平方> = L和多少<= R，尽管如果您知道C ++集合是如何工作的（如果没有，应该这样做），则可以这样做没有那么复杂。