We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Prime Numbers in Range

Difficulty: Medium

Problem Description

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

  • left <= num1 < num2 <= right.
  • Both num1 and num2 are prime numbers.
  • num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].

Key Insights

  • To find the closest prime numbers in a range, we first need to identify all the prime numbers between left and right.
  • A prime number is defined as a number greater than 1 that has no divisors other than 1 and itself.
  • We can use the Sieve of Eratosthenes algorithm to efficiently find all prime numbers up to right.
  • Once we have the list of primes, we can iterate through them to find two consecutive primes that yield the minimum difference.

Space and Time Complexity

Time Complexity: O(n log log n) for the Sieve of Eratosthenes, plus O(k) for checking consecutive primes, where n is right and k is the number of primes found in the range.

Space Complexity: O(n) for storing the boolean array used in the Sieve of Eratosthenes.

Solution

We will use the Sieve of Eratosthenes to generate a list of prime numbers up to right. After generating the primes, we will filter those that fall within the range [left, right]. Then, we will iterate through the filtered prime numbers to find the pair with the smallest difference. If no valid pairs are found, we return [-1, -1].

Code Solutions

def closestPrimes(left: int, right: int) -> List[int]:
    def sieve(n):
        is_prime = [True] * (n + 1)
        is_prime[0], is_prime[1] = False, False
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]

    primes = sieve(right)
    primes_in_range = [p for p in primes if p >= left]

    if len(primes_in_range) < 2:
        return [-1, -1]
    
    min_diff = float('inf')
    ans = [-1, -1]
    
    for i in range(len(primes_in_range) - 1):
        num1, num2 = primes_in_range[i], primes_in_range[i + 1]
        if num2 - num1 < min_diff:
            min_diff = num2 - num1
            ans = [num1, num2]

    return ans
← Back to All Questions