Closest Prime Numbers in Range - Practice Coding Problems

Closest Prime Numbers in Range - Problem

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].

Input & Output

Example 1 — Basic Range

$ Input: left = 4, right = 6

› Output: [5, 5]

💡 Note: Only prime in range [4,6] is 5, but we need two different primes, so no valid pair exists. Wait, that's wrong. Let me recalculate: primes in [4,6] = [5]. Since we need num1 < num2, return [-1, -1]

Example 2 — Twin Primes

$ Input: left = 4, right = 18

› Output: [11, 13]

💡 Note: Primes in range: 5, 7, 11, 13, 17. Gaps: 7-5=2, 11-7=4, 13-11=2, 17-13=4. Minimum gap is 2, first occurrence is [11, 13]

Example 3 — Large Gap

$ Input: left = 20, right = 30

› Output: [23, 29]

💡 Note: Primes in range [20,30]: 23, 29. Only one pair possible: [23, 29] with gap 6

Constraints

1 ≤ left ≤ right ≤ 10⁶
Both left and right are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given range [left=4, right=18]

Find Primes

Locate all primes: 5, 7, 11, 13, 17

Calculate Gaps

Find minimum gap between consecutive primes

Key Takeaway

🎯 Key Insight: Use Sieve of Eratosthenes for efficient prime generation, then scan consecutive primes for minimum gap

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to efficiently find all primes in the range using Sieve of Eratosthenes, then scan consecutive primes to find the minimum gap. The optimal approach uses sieve for O(n log log n) prime generation, then linear scan for closest pair. Time: O(n log log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sieve of Eratosthenes + Linear Scan	O(n log log n)	O(n)	Pre-compute all primes using sieve, then find consecutive primes with minimum gap
Brute Force Prime Checking	O(n²√n)	O(n)	Check every number for primality, then find closest prime pair

Sieve of Eratosthenes + Linear Scan — Algorithm Steps

Step 1: Use Sieve of Eratosthenes to find all primes up to 'right'
Step 2: Filter primes within [left, right] range
Step 3: Scan consecutive primes to find minimum gap

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Sieve

Mark all numbers as potentially prime

Mark Multiples

Cross out multiples of each prime

Find Closest Gap

Scan consecutive primes for minimum gap

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

void solution(int left, int right, int* result) {
    if (right < 2) {
        result[0] = -1;
        result[1] = -1;
        return;
    }
    
    // Sieve of Eratosthenes
    int* sieve = (int*)malloc((right + 1) * sizeof(int));
    for (int i = 0; i <= right; i++) {
        sieve[i] = 1;
    }
    sieve[0] = sieve[1] = 0;
    
    for (int i = 2; i * i <= right; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= right; j += i) {
                sieve[j] = 0;
            }
        }
    }
    
    // Collect primes in range [left, right]
    int* primes = (int*)malloc(10000 * sizeof(int));
    int count = 0;
    
    for (int i = left; i <= right; i++) {
        if (sieve[i]) {
            primes[count++] = i;
        }
    }
    
    if (count < 2) {
        result[0] = -1;
        result[1] = -1;
        free(sieve);
        free(primes);
        return;
    }
    
    // Find minimum gap between consecutive primes
    int minGap = INT_MAX;
    result[0] = -1;
    result[1] = -1;
    
    for (int i = 0; i < count - 1; i++) {
        int gap = primes[i + 1] - primes[i];
        if (gap < minGap) {
            minGap = gap;
            result[0] = primes[i];
            result[1] = primes[i + 1];
        }
    }
    
    free(sieve);
    free(primes);
}

int main() {
    int left, right;
    scanf("%d", &left);
    scanf("%d", &right);
    
    int result[2];
    solution(left, right, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log log n)

Sieve of Eratosthenes is O(n log log n), scanning primes is O(π(n)) where π(n) is prime counting function

⚡ Linearithmic

Space Complexity

O(n)

Boolean array for sieve and list to store primes in range

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sieve of Eratosthenes + Linear Scan — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler