Tightest Prime Pair

Medium

You are given two integers low and high. Among the primes in the range [low, high] (both ends included), find two primes p < q whose difference q - p is as small as possible. Return [p, q]. If several pairs share the smallest difference, pick the one with the smallest p. If the range holds fewer than two primes, return [-1, -1].

Example 1

low=20, high=40 → [29, 31]

The primes in the range are 23, 29, 31 and 37. The smallest gap is 2, between 29 and 31.

Example 2

low=2, high=7 → [2, 3]

2 and 3 differ by just 1, which is as small as it gets.

Example 3

low=24, high=28 → [-1, -1]

There are no primes in the range at all.

Constraints

1 ≤ low ≤ high ≤ 3 · 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Number Theory

Similar problems

Primes Below a Bound Medium Laser in a Mirror Room Medium First Prime That Reads Both Ways Medium N-th Number Divisible by One of Three Medium Reduced Fractions Up to a Denominator Medium

Input

low=20, high=40

Expected

[29, 31]

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.