Problem statement

Given two integers left and right, find two primes num1 < num2 with left <= num1 < num2 <= right whose difference num2 - num1 is as small as possible.

Return [num1, num2]. If several pairs share the minimum difference, return the one with the smallest num1. If the range holds fewer than two primes, return [-1, -1].

Example 1

Input: left = 30, right = 45
Output: [41,43]
Explanation: The primes are 31, 37, 41, 43; the gaps are 6, 4 and 2.

Example 2

Input: left = 24, right = 28
Output: [-1,-1]
Explanation: There is no prime in this range.

Example 3

Input: left = 1, right = 3
Output: [2,3]

Constraints

• 1 <= left <= right <= 10^6

Hints for Closest Prime Numbers in Range

1. Hint 1

   Only consecutive primes in the range can form the closest pair.

2. Hint 2

   Walk through the range, remember the previous prime, and keep the smallest gap seen so far — the first one wins ties automatically.

3. Hint 3

   No two primes differ by less than 2 except 2 and 3, so as soon as you see a gap of 2 (or 1) nothing later can beat it: stop scanning.

How to solve Closest Prime Numbers in Range

Scan the range in increasing order, keeping the previous prime and the best adjacent pair. A gap of at most 2 is unbeatable, and twin primes are common, so the scan usually stops early.

Approach

1. For x from left to right, test whether x is prime by trial division up to √x (odd divisors only after 2).
2. When x is prime and a previous prime prev exists, replace the best pair with [prev, x] if x - prev is strictly smaller than the best gap.
3. If that gap is at most 2, stop — no later pair can be strictly closer.
4. Set prev = x and continue. Return the best pair, or [-1, -1] if none was found.

Why it works

Any pair of primes that is not consecutive has a prime between them, so it is at least as wide as a consecutive pair inside it; checking consecutive pairs is enough. Replacing only on a strictly smaller gap keeps the earliest pair among ties. A gap of 1 occurs only for (2, 3) and every other pair of primes differs by at least 2, so once a gap of 2 is recorded, later pairs can at best tie — and ties keep the earlier pair — which makes the early exit safe.

Complexity

• Time — O((right - left) · √right) in the worst case, far less in practice
• Space — O(1)

Pitfalls

• 1 is not prime; left = 1 must not produce the pair (1, 2).
• Use a strict < when comparing gaps, or a later pair will steal a tie.
• A sieve up to right also works (10^6 entries), but rebuild cost matters if it is called many times — trial division with the early exit avoids it.

Reference solution

Python

from typing import List

def closestPrimes(left: int, right: int) -> List[int]:
    def is_prime(x):
        if x < 2:
            return False
        if x % 2 == 0:
            return x == 2
        d = 3
        while d * d <= x:
            if x % d == 0:
                return False
            d += 2
        return True

    prev = -1
    best = [-1, -1]
    for x in range(left, right + 1):
        if is_prime(x):
            if prev != -1 and (best[0] == -1 or x - prev < best[1] - best[0]):
                best = [prev, x]
                if x - prev <= 2:
                    break
            prev = x
    return best

Java

public static int[] closestPrimes(int left, int right) {
    int prev = -1;
    int[] best = { -1, -1 };
    for (int x = left; x <= right; x++) {
        if (!closeIsPrime(x)) continue;
        if (prev != -1 && (best[0] == -1 || x - prev < best[1] - best[0])) {
            best = new int[] { prev, x };
            if (x - prev <= 2) break;
        }
        prev = x;
    }
    return best;
}

private static boolean closeIsPrime(int x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (int d = 3; d * d <= x; d += 2) if (x % d == 0) return false;
    return true;
}

C++

bool closeIsPrime(int x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (int d = 3; d * d <= x; d += 2) if (x % d == 0) return false;
    return true;
}

vector<int> closestPrimes(int left, int right) {
    int prev = -1;
    vector<int> best = { -1, -1 };
    for (int x = left; x <= right; x++) {
        if (!closeIsPrime(x)) continue;
        if (prev != -1 && (best[0] == -1 || x - prev < best[1] - best[0])) {
            best = { prev, x };
            if (x - prev <= 2) break;
        }
        prev = x;
    }
    return best;
}

JavaScript

var closestPrimes = function(left, right) {
    var isPrime = function(x) {
        if (x < 2) return false;
        if (x % 2 === 0) return x === 2;
        for (var d = 3; d * d <= x; d += 2) if (x % d === 0) return false;
        return true;
    };
    var prev = -1, best = [-1, -1];
    for (var x = left; x <= right; x++) {
        if (!isPrime(x)) continue;
        if (prev !== -1 && (best[0] === -1 || x - prev < best[1] - best[0])) {
            best = [prev, x];
            if (x - prev <= 2) break;
        }
        prev = x;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium