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

, ,

描述

给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。

如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：

  • 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
  • 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。

返回区间 [l, r] 内不是特殊数字的数字数量。

示例 ：

输入： l = 5, r = 7

输出： 3

解释： 区间 [5, 7] 内不存在特殊数字。

提示：

  • 1 <= l <= r <= 10^9

思考

leetcode的第408周赛第2题，通过题目描述，需要寻找有两个真因数的特殊数字，我们可以暴力遍历[1, 1000]区间内的特殊数字。

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    for (int i = 1; i < 1000; i++) {
        int count = 0;
        for(int j = 1; j < i; j++){
            if(i % j == 0) count++;
        }
        if(count == 2) System._out_.println(i);
    }
}

输出结果为

1
2
3
4
5
6
7
8
9
10
11
4
9
25
49
121
169
289
361
529
841
961

可以发现一个共同点，这些数字的除 1 以外的另一个真因数是素数，且这个素数是特殊数字的开方数。

根据这个特点可以推出特殊数字是素数的平方数。因此求的是[√l, √r]区间内的素数的数量。

参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int nonSpecialCount(int l, int r) {
        int low = (int) Math.sqrt(l);
        int up = (int) Math.sqrt(r);

        if(low * low < l) low++;//确保在[√l, √r]的区间内

        int count = 0;
        for(int i = Math.max(low, 2); i <= up; i++){
            if(isPrime(i)) count++;
        }
        return r - l + 1 - count ;
    }
    
    private boolean isPrime(int num){
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }

复杂度分析：

  • 时间复杂度：O(√r * √r)
  • 空间复杂度：O(1)

相关链接

100371. 统计不是特殊数字的数字数量 - 力扣（LeetCode）

yzlzzzdeveloper