<p>Given two positive integers <code>left</code> and <code>right</code>, find the two integers <code>num1</code> and <code>num2</code> such that:</p>

<ul>
	<li><code>left &lt;= num1 &lt; num2 &lt;= right </code>.</li>
	<li><code>num1</code> and <code>num2</code> are both <strong>prime</strong> numbers.</li>
	<li><code>num2 - num1</code> is the <strong>minimum</strong> amongst all other pairs satisfying the above conditions.</li>
</ul>

<p>Return <em>the positive integer array</em> <code>ans = [num1, num2]</code>. <em>If there are multiple pairs satisfying these conditions, return the one with the minimum</em> <code>num1</code> <em>value or</em> <code>[-1, -1]</code> <em>if such numbers do not exist.</em></p>

<p>A number greater than <code>1</code> is called <b>prime</b> if it is only divisible by <code>1</code> and itself.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> left = 10, right = 19
<strong>Output:</strong> [11,13]
<strong>Explanation:</strong> The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> left = 4, right = 6
<strong>Output:</strong> [-1,-1]
<strong>Explanation:</strong> There exists only one prime number in the given range, so the conditions cannot be satisfied.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 10<sup>6</sup></code></li>
</ul>

<p>&nbsp;</p>
<style type="text/css">.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0; 
}
.spoiler {overflow:hidden;}
.spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
.spoilerbutton[value="Show Message"] + .spoiler > div {margin-top:-500%;}
.spoilerbutton[value="Hide Message"] + .spoiler {padding:5px;}
</style>

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:

        # SHORTCUT: assume X, Y, and Z are primes, X < Y < Z.
        # (Z - X) === (Y - X) + (Z - Y)
        # each of these differences is a nonnegative number.
        # Therefore Z-X will be larger than either of the other two,
        # and can be ignored.  This means we only care about differences
        # between *pairs of adjacent* primes, rather than any other pairing.

        # these two functions are from IterTools Recipes:
        # https://docs.python.org/3/library/itertools.html

        import contextlib

        def iter_index(iterable, value, start=0, stop=None):
            "Return indices where a value occurs in a sequence or iterable."
            # iter_index('AABCADEAF', 'A') → 0 1 4 7
            seq_index = getattr(iterable, 'index', None)
            if seq_index is None:
                iterator = islice(iterable, start, stop)
                for i, element in enumerate(iterator, start):
                    if element is value or element == value:
                        yield i
            else:
                stop = len(iterable) if stop is None else stop
                i = start
                with contextlib.suppress(ValueError):
                    while True:
                        yield (i := seq_index(value, i, stop))
                        i += 1

        def sieve(n):
            "Primes less than n."
            # sieve(30) → 2 3 5 7 11 13 17 19 23 29
            if n > 2:
                yield 2
            data = bytearray((0, 1)) * (n // 2)
            for p in iter_index(data, 1, start=3, stop=math.isqrt(n) + 1):
                data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))
            yield from iter_index(data, 1, start=3)

        prior_prime = None
        best_diff = float('+inf')
        answer = [-1, -1]
        for prime in sieve(right + 1):
            if prime < left:
                # print(f'{prime=} (low)')
                continue
            if prior_prime is None:
                print(f'{prior_prime} {prime} (first) {answer=}')
                prior_prime = prime
                continue
            diff = prime - prior_prime
            if best_diff > diff:
                # strict ">" so we choose the lower pair when equal
                best_diff = diff
                answer = [prior_prime, prime]
            print(f'{prior_prime} {prime} {diff=} {answer=}')
            if diff == 2:
                print(f'  BEST POSSIBLE ANSWER')
                break
            prior_prime = prime
        
        return answer

16993