原题:

https://leetcode.cn/problems/find-the-count-of-numbers-which-are-not-special/description/

描述:

给你两个 *正整数 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 <= 1 <= r <= 10^9

个人版答案

执行用时: 76 ms 执行内存消耗: 40 M

class Solution {
    public int nonSpecialCount(int l, int r) {
        int start = (int) Math.ceil(Math.sqrt(l));
        int end = (int) Math.floor(Math.sqrt(r));
        int c = 0;
      
        for (int i = start; i <= end; i++) {
            if (i * i >= l && i * i <= r) {
                if (isPrime(i)) {
                    c++;
                }
            }
        }

        return r - l + 1 - c;
    }

    public static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

优秀解法

执行耗时: 2 ms

class Solution {
    private static final List<Integer> primePower = new ArrayList<>();
    private static final int n;

    static {
        // 方法一:埃式筛
        int MAX = 31623;
        boolean[] np = new boolean[MAX + 1];
        for (int i = 2; i <= MAX; i++) {
            if (!np[i]) {
                // 质数
                primePower.add(i * i);
                int a;
                for (int j = i; (a = i * j) <= MAX; j++) {
                    np[a] = true;
                }
            }
        }
        n = primePower.size();
    }

    public int nonSpecialCount(int l, int r) {
        // 1)  >=6 的偶数一定不是特殊数字 至少有1，2 和 n/2 3个真因数
        // 2)  质数一定不是特殊数字, 只有1个真因数
        // 1 2 3 4 5 中  只有 4 是 特殊数字（2个真因素1, 2）
        // n 除了1以外只有一个真因子 a * a = n  a > 1  且 a是质数
        // 问题转化为[l,r]内不是质数平方数的个数
        // a * a >=l
        int t = binarySearch(-1, n, r + 1) - binarySearch(-1, n, l);
        return r - l + 1 - t;
    }

    // 返回 primeArr中 平方数>= t 的最小下标
    private int binarySearch(int l, int r, int t) {
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (primePower.get(mid) >= t) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}

个人解题思路与优秀答案解析

题目分析及个人版思路

1. 没看懂...再看一眼
2. 这说的是什么玩意儿?
3. 嗷... 就是质数平方数在区间呗...说人话真难.
4. 3容易理解不? 为啥是质数平方. 因为按照题目要求, x的所有正因数除了自己叫真因数, 恰好有俩的时候这个数就是特殊数字了.
5. 那为什么是质数不是合数? 因为只有质数的平方的因数才是 1 和 这个质数. 比如 例子里的4 是特殊数字. 可以写成2^2. 那么2 只有 1和2两个因子. 对 4 来说. 除了自己之外, 也就只有1 和 2 了.
6. 那我们很容易验证, 第二个例子的6 . 因为一眼不是质数平方. 我们计算因子, 就是 1 2 3 了.
7. 下一个验证一下 9 . 是不是只有 1 和 3?
8. 思路出现. 开始撸代码. 详见代码块
9. 为什么做了个开方? 因为要计算区间内的个数, 只需要对两侧数字开平方. 左边 向上取整, 右边向下取整即可获得一个平方区间. 我们很容易就可以在这个区间内找出所有质数...return 齐活.

进阶版思路
埃式筛??? 每天一个没见过的新玩意儿... 反正人家就是快...是埃氏筛和二分查找???哎...这是本渣仰望的高度啊