Problem

You are given 2 positive integers l and r. For any number x, all positive divisors of x except x are called the proper divisors of x.

A number is called special if it has exactly 2 proper divisors. For example:

  • The number 4 is special because it has proper divisors 1 and 2.
  • The number 6 is not special because it has proper divisors 1, 2, and 3.

Return the count of numbers in the range [l, r] that are not special.

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

Example 1:

Input: l = 5, r = 7
Output: 3
Explanation:
There are no special numbers in the range [5, 7].

Example 2:

Input: l = 4, r = 16
Output: 11
Explanation:
The special numbers in the range [4, 16] are 4 and 9.

Constraints:

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

Test Cases

1
2
class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
solution_test.py
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
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('l, r, expected', [
    (5, 7, 3),
    (4, 16, 11),

    (1, 500**2, 500**2 - 95),
    (1, 1000**2, 1000**2 - 168),
    (1, 1009**2, 1009**2 - 169),
    (1, 30000**2, 30000**2 - 3245),
    (500**2, 30000**2, (30000**2 - 500**2 + 1) - (3245 - 95)),

    (19122653, 68803552, 49680455),
    (10086764, 96508040, 86420515),
])
class Test:
    def test_solution(self, l, r, expected):
        sol = Solution()
        assert sol.nonSpecialCount(l, r) == expected

    def test_solution2(self, l, r, expected):
        sol = Solution2()
        assert sol.nonSpecialCount(l, r) == expected

Thoughts

「特殊数」就是质数的平方。相当于先求出 [l', r'] 内质数的个数，其中 l′=⌈l⌉l'=\lceil\sqrt l\rceil、r′=⌊r⌋r'=\lfloor\sqrt r\rfloor。

判断自然数 n 是不是质数，需看所有的 2 <= i <= √n，n 能否被 i 整除，时间复杂度 O(√n)。

如果已经有了所有小于等于 √n 的质数集合，可以遍历已知的质数，看能否被 n 整除，时间复杂度约为 O(n/ln⁡n)O(\sqrt n/\ln\sqrt n)。

根据 质数定理 可知，n 以内的质数个数为 π(n)≈n/ln⁡n\pi(n)≈n/\ln n。

判断连续多个自然数是否是质数，可以考虑把已知的质数保存起来。

判断 [l', r'] 内质数的个数，如果不缓存已知的质数表，需要时间大约是 ∑i=l′r′i\sum_{i=l'}^{r'}\sqrt i。如果要用质数表，需要从 1 开始构建，需要的时间大约是 ∑i=1r′(i/ln⁡i)\sum_{i=1}^{r'}(\sqrt i/\ln\sqrt i)。

粗估下来，对于限定的 1 <= l <= r <= 10^9 范围，当 r' > l' + 10 时，从 1 开始构建质数表就更划算。

Code

solution.py
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from math import ceil


class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        primes = [
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
            71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
            167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
            271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
            389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
            503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619,
            631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751,
            757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
            883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
        ]

        def is_prime(x: int) -> bool:
            sqrt_x = int(x ** 0.5)
            for p in primes:
                if p > sqrt_x:
                    primes.append(x)
                    return True
                if x % p == 0:
                    return False

        total = r - l + 1
        l = ceil(l ** 0.5)
        r = int(r ** 0.5)

        # Counting prime number in [l, r].
        cnt_l = 0 # Count of prime numbers less than l.
        cnt_r = 0 # Count of prime numbers less than or equal to r.

        for p in primes:
            if p > r:
                break
            cnt_r += 1
            if p < l:
                cnt_l += 1

        for n in range(1001, r+1, 2):
            if is_prime(n):
                cnt_r += 1
                if n < l:
                    cnt_l += 1

        return total - (cnt_r - cnt_l)

在 LeetCode 上提交的话，一个可选的作 bú 弊 shì 方案是把质数表缓存到 Solution.nonSpecialCount 之外，甚至直接提前先算好整个质数表（上限取 ⌊1e9⌋=31622\lfloor\sqrt{1e9}\rfloor=31622 即可），并进一步计算出所有的 π(n)\pi(n)（小于 n 的质数个数），在 Solution.nonSpecialCount 里用常数时间计算 π(r′+1)−π(l′)\pi(r'+1)-\pi(l') 即可。

solution2.py
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
31
from math import ceil

LIMIT = 31622 + 1
counts = [0] * LIMIT
primes = [2]

def is_prime(x: int) -> bool:
    sqrt_x = int(x ** 0.5)
    for p in primes:
        if p > sqrt_x:
            primes.append(x)
            return True
        if x % p == 0:
            return False

counts[2] = 1
for n in range(3, LIMIT):
    counts[n] = counts[n-1]
    if n & 1 and is_prime(n):
        counts[n] += 1


class Solution:
    def nonSpecialCount(self, l: int, r: int) -> int:
        total = r - l + 1
        l = ceil(l ** 0.5)
        r = int(r ** 0.5)

        cnt_l = counts[l-1]
        cnt_r = counts[r]
        return total - (cnt_r - cnt_l)
medium
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~