šŸ” Finding the Closest Prime Numbers in a Range using the Sieve of Eratosthenes (leetcode - 2523)

šŸ” Finding the Closest Prime Numbers in a Range using the Sieve of Eratosthenes

Prime numbers play a crucial role in number theory and various computational applications. In this blog, we will explore an optimized approach to finding the two closest prime numbers within a given range using the Sieve of Eratosthenes. šŸš€

šŸ“Œ Problem Statement

Given two integers left and right, find the two prime numbers within the range [left, right] that have the smallest difference. If there are fewer than two prime numbers, return [-1, -1].

šŸ› ️ Approach

To efficiently solve this problem, we use the Sieve of Eratosthenes algorithm to precompute prime numbers up to right. Then, we extract the prime numbers from the given range and find the closest pair.

✅ Steps to Solve

  1. Initialize a boolean list primes where primes[i] = True indicates i is prime.
  2. Mark 0 and 1 as False (not prime).
  3. Use the Sieve of Eratosthenes to eliminate non-prime numbers.
  4. Extract prime numbers from the given range [left, right].
  5. Iterate through the primes to find the pair with the smallest difference.
  6. Return the closest prime pair or [-1, -1] if there are fewer than two primes.

šŸ“œ Code Implementation


from typing import List

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        # Sieve of Eratosthenes
        primes = [True] * (right + 1)
        primes[0], primes[1] = False, False
        for i in range(2, int(right * 0.5) + 1):
            if primes[i]:
                for j in range(i * i, right + 1, i):
                    primes[j] = False
        
        # find primes from the given range
        primes_range = [i for i in range(left, right + 1) if primes[i]]
        # length of prime numbers
        n = len(primes_range)
        closest_pair = [-1, -1]
        # check the length
        if n < 2:
            return closest_pair
        # maximum value
        min_dif = float('inf')
        # checking for minimum difference
        for i in range(n - 1):
            dif = primes_range[i + 1] - primes_range[i]
            if dif < min_dif:
                min_dif = dif
                closest_pair = [primes_range[i], primes_range[i + 1]]
        # return the final value
        return closest_pair

⏳ Complexity Analysis

  • Sieve of Eratosthenes: O(N log log N)
  • Extracting primes in the range: O(N)
  • Finding the closest pair: O(K) (where K is the number of primes in range)
  • Overall Complexity: O(N log log N)

šŸ“Š Example Walkthrough

Input:

left = 10, right = 50

Output:

[11, 13]

Explanation:

Primes in range [10, 50]: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]. The closest pair is (11, 13) with a difference of 2.

šŸš€ Conclusion

The Sieve of Eratosthenes provides an efficient way to compute prime numbers, making this approach optimal for large values of right. By leveraging this algorithm, we can quickly find the closest prime numbers in a given range.

Hope you found this useful! Happy coding! šŸŽÆ

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more