What is the recommended method to find primes efficiently in this problem?

Use the Sieve of Eratosthenes to mark all primes up to right, enabling fast lookups and minimal gap computation.

How do I handle ranges with fewer than two primes?

Return [-1, -1] since no valid pair can exist in these cases.

Does the problem Closest Prime Numbers in Range require checking every number individually?

No, iterating only over primes generated by the sieve avoids unnecessary checks and improves performance.

What if multiple prime pairs have the same minimal difference?

Select the pair with the smaller first prime num1 according to the problem requirement.

What is the time complexity pattern for this number theory problem?

Generating primes up to right using a sieve gives roughly O(min(1452, right-left) * sqrt(right)), optimized over naive primality tests.

#2523

Medium

auto_awesome数学·结合·number·theory

LeetCode 题解工作台

范围内最接近的两个质数

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足： left 。 nums1 和 nums2 都是质数。 nums2 - nums1 是满足上述条件的质数对中的最小值。请你返回正整数数组 ans = [nums1, nums2] 。如果有多个…

数学数论

题目描述

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

left <= nums1 < nums2 <= right 。
nums1 和 nums2 都是质数。
nums2 - nums1 是满足上述条件的质数对中的 最小值 。

请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

示例 1：

输入：left = 10, right = 19
输出：[11,13]
解释：10 到 19 之间的质数为 11 ，13 ，17 和 19 。
质数对的最小差值是 2 ，[11,13] 和 [17,19] 都可以得到最小差值。
由于 11 比 17 小，我们返回第一个质数对。

示例 2：

输入：left = 4, right = 6
输出：[-1,-1]
解释：给定范围内只有一个质数，所以题目条件无法被满足。

提示：

1 <= left <= right <= 10⁶

lightbulb

解题思路

方法一：线性筛

对于给定的范围 $[\textit{left}, \textit{right}]$ ，我们可以使用线性筛求出所有质数，然后从小到大遍历质数，找到相邻的两个质数，其差值最小的质数对即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n = \textit{right}$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        cnt = 0
        st = [False] * (right + 1)
        prime = [0] * (right + 1)
        for i in range(2, right + 1):
            if not st[i]:
                prime[cnt] = i
                cnt += 1
            j = 0
            while prime[j] <= right // i:
                st[prime[j] * i] = 1
                if i % prime[j] == 0:
                    break
                j += 1
        p = [v for v in prime[:cnt] if left <= v <= right]
        mi = inf
        ans = [-1, -1]
        for a, b in pairwise(p):
            if (d := b - a) < mi:
                mi = d
                ans = [a, b]
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(min(1452, right-left) * sqrt(right)) due to prime checking using the Sieve. Space complexity is O(1) beyond the prime markers, since only previous prime and minimal gap need tracking.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Expect optimized prime generation rather than naive primality checks.
question_mark
Look for minimal gap handling to ensure correct pair selection.
question_mark
Check edge cases where the range has fewer than two primes.

warning

常见陷阱

外企场景

error
Not handling single-prime or empty ranges and returning invalid pairs.
error
Failing to track the previous prime correctly, causing incorrect minimal gap results.
error
Assuming consecutive numbers are primes instead of iterating through the sieve results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the farthest prime numbers in a given range instead of the closest.
arrow_right_alt
Return all prime pairs with the same minimal gap within a range.
arrow_right_alt
Compute the closest prime pair in a very large range efficiently using segmented sieve.

help

常见问题

外企场景

继续练习

#2521 数组乘积中的不同质因数数目 #2513 最小化两个数组中的最大值 #2507 使用质因数之和替换后可以取到的最小值