跳转至

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 <= 109

解法

方法一：数学

根据题目描述，我们可以发现，只有质数的平方才是特殊数字。因此，我们可以先预处理出小于等于 $\sqrt{10^9}$ 的所有质数，然后遍历区间 $[\lceil\sqrt{l}\rceil, \lfloor\sqrt{r}\rfloor]$，统计出区间内的质数个数 $\textit{cnt}$，最后返回 $r - l + 1 - \textit{cnt}$ 即可。

时间复杂度 $O(\sqrt{m})$，空间复杂度 $O(\sqrt{m})$。其中 $m = 10^9$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
m = 31623
primes = [True] * (m + 1)
primes[0] = primes[1] = False
for i in range(2, m + 1):
    if primes[i]:
        for j in range(i + i, m + 1, i):
            primes[j] = False


class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        lo = ceil(sqrt(l))
        hi = floor(sqrt(r))
        cnt = sum(primes[i] for i in range(lo, hi + 1))
        return r - l + 1 - cnt

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    static int m = 31623;
    static boolean[] primes = new boolean[m + 1];

    static {
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;
        for (int i = 2; i <= m; i++) {
            if (primes[i]) {
                for (int j = i + i; j <= m; j += i) {
                    primes[j] = false;
                }
            }
        }
    }

    public int nonSpecialCount(int l, int r) {
        int lo = (int) Math.ceil(Math.sqrt(l));
        int hi = (int) Math.floor(Math.sqrt(r));
        int cnt = 0;
        for (int i = lo; i <= hi; i++) {
            if (primes[i]) {
                cnt++;
            }
        }
        return r - l + 1 - cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int m = 31623;
bool primes[m + 1];

auto init = [] {
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    for (int i = 2; i <= m; ++i) {
        if (primes[i]) {
            for (int j = i * 2; j <= m; j += i) {
                primes[j] = false;
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int lo = ceil(sqrt(l));
        int hi = floor(sqrt(r));
        int cnt = 0;
        for (int i = lo; i <= hi; ++i) {
            if (primes[i]) {
                ++cnt;
            }
        }
        return r - l + 1 - cnt;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const m = 31623

var primes [m + 1]bool

func init() {
    for i := range primes {
        primes[i] = true
    }
    primes[0] = false
    primes[1] = false
    for i := 2; i <= m; i++ {
        if primes[i] {
            for j := i * 2; j <= m; j += i {
                primes[j] = false
            }
        }
    }
}

func nonSpecialCount(l int, r int) int {
    lo := int(math.Ceil(math.Sqrt(float64(l))))
    hi := int(math.Floor(math.Sqrt(float64(r))))
    cnt := 0
    for i := lo; i <= hi; i++ {
        if primes[i] {
            cnt++
        }
    }
    return r - l + 1 - cnt
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const m = 31623;
const primes: boolean[] = Array(m + 1).fill(true);

(() => {
    primes[0] = primes[1] = false;
    for (let i = 2; i <= m; ++i) {
        if (primes[i]) {
            for (let j = i * 2; j <= m; j += i) {
                primes[j] = false;
            }
        }
    }
})();

function nonSpecialCount(l: number, r: number): number {
    const lo = Math.ceil(Math.sqrt(l));
    const hi = Math.floor(Math.sqrt(r));
    let cnt = 0;
    for (let i = lo; i <= hi; ++i) {
        if (primes[i]) {
            ++cnt;
        }
    }
    return r - l + 1 - cnt;
}

评论