What is the definition of a special number in this problem?

A special number is a number that is the square of a prime number.

How do I efficiently find prime numbers in the range [l, r]?

You can use a sieve algorithm to generate primes up to sqrt(r) and then check if the square roots of numbers in [l, r] are prime.

What is the pattern used in this problem?

This problem combines Array and Math patterns, particularly focusing on identifying squares of prime numbers.

How can I optimize my solution for large inputs?

By using a sieve to precompute primes up to sqrt(r) and checking each number's square root efficiently, you can handle larger inputs effectively.

What is the expected time complexity for this problem?

The time complexity depends on the method used for prime checking and the size of the range [l, r]. A sieve-based approach can make it feasible for large inputs.

#3233

Medium

auto_awesome数组·数学

LeetCode 题解工作台

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

给你两个正整数 l 和 r 。对于任何数字 x ， x 的所有正因数（除了 x 本身）被称为 x 的真因数。如果一个数字恰好仅有两个真因数，则称该数字为特殊数字。例如：数字 4 是特殊数字，因为它的真因数为 1 和 2。数字 6 不是特殊数字，因为它的真因数为 1、2 和…

数组数学数论

题目描述

给你两个 正整数 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⁹

lightbulb

解题思路

方法一：数学

根据题目描述，我们可以发现，只有质数的平方才是特殊数字。因此，我们可以先预处理出小于等于 $\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

16

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate can efficiently handle the identification of prime numbers.
question_mark
Look for understanding of number theory concepts like divisors and prime squares.
question_mark
Assess the candidate's ability to optimize the solution for large ranges of numbers.

warning

常见陷阱

外企场景

error
Misidentifying numbers as special when they are not squares of primes.
error
Inefficient prime checking methods that lead to slower performance on large ranges.
error
Failing to account for edge cases, such as very small or very large values of l and r.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Optimize the solution for very large ranges, e.g., when l and r are close to 109.
arrow_right_alt
Consider variations where the definition of special numbers changes, such as requiring more than two divisors.
arrow_right_alt
Change the problem to count the special numbers instead of the non-special ones.

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #3326 使数组非递减的最少除法操作次数 #3334 数组的最大因子得分