# 2523. Closest Prime Numbers in Range
###### tags: `Leetcode` `Medium` `Math` `Prime Factors`
Link: https://leetcode.com/problems/closest-prime-numbers-in-range/description/
## 思路
### 思路一
对于```left```到```right```的每一个数都判断一下是不是prime

不断更新```diff```和```start``` 
如果发现遍历完之后```last==-1```或者```start==-1``` 说明没有凑够两个prime 直接返回```[-1,-1]```
否则返回```[start, start+diff]```
以上是常规思路 如果按上面的方法做就会TLE
但是可以加一些trick
因为我们知道最小的prime差是1(2和3) 其次是2 prime差是2的prime pairs有很多对 所以我们一旦找到一个prime差小于等于2的pair就可以直接返回 不需要往后找了
### 思路二
用[Sieve of Eratosthenes](https://www.geeksforgeeks.org/sieve-of-eratosthenes/)方法找到一个范围内的所有prime 然后再用类似思路一的方法找到间隔最小的两个prime
## Code
### 思路一

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

def isPrime(num: int) -> bool:
if num==1: return False
for i in range(2, int(math.sqrt(num))+1):
if num%i==0: return False
return True

last = -1
diff = 1e6
start = -1
for i in range(left, right+1):
if not isPrime(i): continue
if last!=-1:
if diff>i-last:
diff = i-last
start = last
if diff<=2: return [start, start+diff]
last = i
if last==-1 or start==-1:
return [-1, -1]
else: return [start, start+diff]

### 思路二

class Solution:
def closestPrimes(self, left: int, right: int) -> List[int]:
def sieve(left: int, right: int):
prime = [True]*(right+1)
prime[0] = False
prime[1] = False
for i in range(2, int(math.sqrt(right))+1):
if prime[i]:
for j in range(i*i ,right+1 ,i):
prime[j] = False
return [i for i in range(left, right+1) if prime[i]]
primes = sieve(left, right)
if len(primes)<2: return [-1, -1]
last = -1
diff = math.inf
start = -1
for i in primes:
if last!=-1:
if diff>i-last:
diff = i-last
start = last
if diff<=2:
return [start, start+diff]
last = i
return [start, start+diff]