2523

2523. Closest Prime Numbers in Range (Medium)

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

 

Companies: TikTok

Related Topics:
Math, Number Theory

Similar Questions:

• Count Ways to Make Array With Product (Hard)

Solution 1. Sieve of Eratosthenes

// OJ: https://leetcode.com/problems/closest-prime-numbers-in-range
// Author: github.com/lzl124631x
// Time: O(NloglogN)
// Space: O(N)
class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        vector<bool> isPrime(right + 1, true);
        vector<int> primes;
        int bound = sqrt(right), minDiff = INT_MAX, first = -1;
        for (int i = 2; i <= right; ++i) {
            if (!isPrime[i]) continue;
            if (i >= left) primes.push_back(i);
            if (i > bound) continue;
            for (int j = i * i; j <= right; j += i) isPrime[j] = false;
        }
        for (int i = 1; i < primes.size(); ++i) {
            int d = primes[i] - primes[i - 1];
            if (d < minDiff) {
                minDiff = d;
                first = i - 1;
            }
        }
        return first == -1 ? vector<int>{-1,-1} : vector<int>{primes[first], primes[first + 1]};
    }
};