【从零开始的LeetCode-算法】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

我的解答：

class Solution {
    public int nonSpecialCount(int l, int r) {
        int res = r - l + 1;
        int n = (int)  Math.sqrt(r);
        int[] prime_number = new int[n + 1];
        // 单独判断范围内是否包含4
        if(l <=4 && r>=4) res--;
        // 从3开始遍历奇数，因为偶数都能被2整除
        for(int i = 3; i <= n; i+=2){
            // 判断i是否是质数
            if(prime_number[i] == 0){
                // 如果该质数的乘积在【l，r】范围内，则表示范围内有一个特殊数字i*i，需要减一
                if(i*i >=l && i*i <= r){
                    res--;
                }
                // 后面所有i的倍数都是质数，因为能被i整除
                for(int j = i * 2;j <= n;j += i){
                    prime_number[j] = 1;
                }
            }
        }
        return res;
    }
}