# Problem Statement
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]`_._
## Constraints
- `1 <= left <= right <= 10^6`
# Solution
Since we can write code outside of Leetcode's `Solution` class, we can declare variables that will persist throughout test cases. Using this knowledge we can use a [[Sieve of Eratosthenes|prime sieve]] to quickly get all [[Prime numbers|primes]] from `2` to `10^6`.
```python
N = 1000000
sieve = [True]*(N+1)
sieve[1] = False
for i in range(2, int(sqrt(N))):
if not sieve[i]: continue
for j in range(i*i, N, i):
sieve[j] = False
P = [i for i in range(N+1) if sieve[i]]
```
For the test cases, we need to check adjacent pairs of primes from `left` to `right`. We can use [[Binary Search]] to find the first index greater than or equal to `left` in `O(log(n))`. Then we use [[itertools.pairwise]] to check adjacent primes and store the best result. Once we've gone too far we return the best found so far or `[-1,-1]` if there weren't enough primes.
```python
start = bisect_left(P, left)
best = 9999999
ans = [-1,-1]
while True:
try: a,b = P[start], P[start + 1]
except: break
if b > right:
break
if b-a < best:
best = b-a
ans = [a,b]
start += 1
return ans
```
Time Complexity: O$(n \log \log n)$ | Space Complexity: O$(n)$