目标
给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。
如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：
- 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
- 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。
返回区间 [l, r] 内 不是 特殊数字 的数字数量。
示例 1：
输入： l = 5, r = 7
输出： 3
解释：
区间 [5, 7] 内不存在特殊数字。示例 2：
输入： l = 4, r = 16
输出： 11
解释：
区间 [4, 16] 内的特殊数字为 4 和 9。说明：
- 1 <= l <= r <= 10^9
提示：
- A special number must be a square of a prime number.
- We need to find all primes in the range [sqrt(l), sqrt(r)].
- Use sieve to find primes till sqrt(10^9).
思路
返回给定区间 [l, r] 内不是特殊数字的数字个数，所谓特殊数字指除了它本身恰好有两个正因数的数字。
一看到数据范围是 10^9 就不可能使用使用暴力解法去判断每一个数字是不是 l 或 r 的因数，要么使用二分要么预处理。特殊数字是确定的，它除了自身以外只有两个因数，1 一定是一个，即除了 1 和它本身只有一个因数。看了提示说特殊数字是质数的平方，我们需要找到所有在 [√l, √r] 范围内的质数，可以预处理 √10^9 内的质数。二分查找 [l, r] 范围内质数的个数，然后减掉即可。
埃氏筛的基本思想是创建一个 boolean[] 标记查询范围内的数是否为质数，初始时均标记为 true。从 2 开始遍历（0和 1 后面直接过滤掉了)，直到 i < √end 即 i * i < end。在循环内部，如果当前值是质数，则将 i * i，i * (i + 1)，i * (i + 2)，…… 标记为非质数。比如在 2 的循环内，所有大于 2 的偶数都被标为非质数，以此类推，像筛子一样将质数筛选出来。
// todo 最后也可以使用前缀和计算个数
代码
/**
* @date 2024-11-22 9:07
*/
public class NonSpecialCount3233 {
public static int[] primes;
static {
List<Integer> primeList = new ArrayList<>();
int end = (int) Math.ceil(Math.sqrt(1000000001));
boolean[] isPrime = new boolean[end + 1];
Arrays.fill(isPrime, true);
for (int i = 2; i * i <= end; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= end; j += i) {
isPrime[j] = false;
}
}
}
// 前面没有将 isPrime[0] isPrime[1] 置为false，这里从2开始
for (int i = 2; i <= end; i++) {
if (isPrime[i]) {
primeList.add(i);
}
}
int cnt = primeList.size();
primes = new int[cnt];
for (int i = 0; i < cnt; i++) {
primes[i] = primeList.get(i);
}
}
public int nonSpecialCount_v1(int l, int r) {
int ceilLeft = (int) Math.ceil(Math.sqrt(l));
int right = (int) Math.sqrt(r);
if (ceilLeft > right) {
return r - l + 1;
}
int a = Arrays.binarySearch(primes, ceilLeft);
if (a < 0) {
// 获取插入点，说明原来该位置的值大于ceilLeft
a = -a - 1;
}
int b = Arrays.binarySearch(primes, right);
if (b < 0) {
// 这里多减了1，因为插入点是第一个大于right的位置，减1则小于 right
b = -b - 2;
}
// return r - l + 1 - (b - a + 1);
return r - l - b + a;
}
}
性能
