3233. 统计不是特殊数字的数字数量

链接: 3233. 统计不是特殊数字的数字数量

给你两个 正整数 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

题解

预处理质数+O(1)回答

正难则反: 不是特殊数字 = 全部数字 - 特殊数字

并且注意到:

$特殊数字 = (质数_{_A})^2$

时间复杂度: 预处理: $O(nloglogn)$, 使用: $O(1)$

const int MX = 31622;
int pi[MX + 1]; // pi[i] 的意思是 到第i个数字 有多少个 质数

auto init = [] {
    for (int i = 2; i <= MX; i++) {
        if (pi[i] == 0) { // i 是质数
            pi[i] = pi[i - 1] + 1;
            for (int j = i * i; j <= MX; j += i) {
                pi[j] = -1; // 标记 i 的倍数为合数
            }
        } else {
            pi[i] = pi[i - 1];
        }
    }
    return 0;
}();

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        return r - l + 1 - (pi[(int) sqrt(r)] - pi[(int) sqrt(l - 1)]);
    }
};

C++