Press "Enter" to skip to content

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

Given two positive integers left and right, find the two integers num1 and num2 such that:

  • left <= nums1 < nums2 <= right .
  • nums1 and nums2 are both prime numbers.
  • nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [nums1, nums2]If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

  • 1 <= left <= right <= 106

Solution: Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all primes in range [0, right].

Check neighbor primes and find the best pair.

Time complexity: O(nloglogn)
Space complexity: O(n)

C++

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply