<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 __init__(self):
    self.primes = []

  def set_primes(self, n: int):
    # Create a list of boolean values, prime[i] will be True if i is a prime
    self.primes = [True] * (n + 1)
    self.primes[0] = self.primes[1] = False  # 0 and 1 are not prime numbers

    p = 2
    while (p * p <= n):
      if self.primes[p]:
        for i in range(p * p, n + 1, p):
          self.primes[i] = False
      p += 1

  def closestPrimes(self, l: int, r: int) -> [int, int]:
    def findPrimes(n: int):
      # Init numbers[0] and numbers[1] as False because 0 and 1 are not prime.
      # Init numbers[2] through numbers[n-1] as True because we assume each number
      # is prime until we find a prime number (p) that is a divisor of the number
      numbers = [False if i < 2 else True for i in range(n+1)]
      for p in range(2, int(math.sqrt(n)) + 1):
        if not numbers[p]:
          continue
        # Set all multiples of p to false because they are not prime.
        for multiple in range(p * p, n+1, p):
          numbers[multiple] = False

      # numbers[index] will only be true where index is a prime number
      # return the number of indices whose value is true.
      return numbers

    primes = findPrimes(r)  # find all primes up to r
    pre = -1  # previously encountered prime number
    ans = [-1, -1]  # default answer if no closest pair found

    for i in range(l, r + 1):
      if not primes[i]:
        continue
      if pre != -1 and (ans[0] == -1 or i - pre < ans[1] - ans[0]):
        ans = [pre, i]
      pre = i

    return ans
23376