题目：
给你两个 正整数 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 <= 109
没有技巧的暴力
思路：
直接暴力判断每个数是不是特殊数字即可
代码：
class Solution {
public:
bool isSpecial(int num) {
int cnt = 1;
for (int i = 2; i < num; i++) {
if (num % i == 0) cnt++;
}
return cnt != 2;
}
int nonSpecialCount(int l, int r) {
int ans = 0;
for (int i = l; i <= r; i++) {
if (isSpecial(i)) ans++;
}
return ans;
}
};
质数筛
思路：
特殊数字首先是一个平方数，并且除去自身和 1 之后的另一个因子一定是一个质数。这是因为：
因子一般是成双成对的，若一个数字有奇数个因子，那么该数一定是平方数。
该数除去自身和 1 仅有一个因子，因此该因子一定是质数。
因此，我们可以在 [1, r] 的范围内遍历所有质数，然后将它们的平方从 [l,r] 的范围中去除即可。
由于 r 的范围不超过 1e9 ，因此质数的遍历范围不超过 31622，而使用很简单的埃氏筛（复杂度为 O(nlognlogn)，其中 n 为质数遍历范围）就可以轻松通过本题。
代码：
class Solution {
public:
int nonSpecialCount(int l, int r) {
int n = sqrt(r);
vector<int> v(n + 1);
int res = r - l + 1;
for (int i = 2; i <= n; i++) {
if (v[i] == 0) {
if (i * i >= l && i * i <= r) {
res--;
}
for (int j = i * 2; j <= n; j += i) {
v[j] = 1;
}
}
}
return res;
}
};