# https://leetcode.com/problems/closest-prime-numbers-in-range

from typing import List

class Solution:
    def sieve(self, n):
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for k in range(2, int(n**0.5) + 1):
            if is_prime[k]:
                for multiple in range(k *k, n + 1, k):
                    is_prime[multiple] = False
        return [num for num, prime in enumerate(is_prime) if prime]


    def closestPrimes(self, left: int, right: int) -> List[int]:
        sieve = self.sieve(right)
        result: List[int] = [-1, -1]
        nums = [num for num in sieve if num >= left]
        min = float('inf')
        for i in range(len(nums) - 1 ):
            d = nums[i + 1] - nums[i]
            if min > d:
                result = [nums[i], nums[i + 1]]
                min = d
        return result