Closest Prime Numbers in Range - Leetcode 2523 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:50 - Coding Explanation
8:10 - Drawing Explanation
21:55 - Coding Explanation

leetcode 2523

#neetcode #leetcode #python

[ashmeetsmonga]

The reason that other solutions are super fast is because what they are doing is calculating all primes upto the given upper limit i.e. 10^6 once at the beginning. Then they are just reusing the calculated primes array to get primes instead of calculating primes again and again for each test case. Not useful in case of interview but works here...

[randomystick]

sieve of eratosthenes code (transcribed from the video), for anyone compiling their leetcode flashcard deck:

sieve = [True] * (maxN+1)
sieve[0] = sieve[1] = False

for i in range(2, math.floor(sqrt(maxN))+1):
if not sieve[i]:
continue
for cur in range(2*i, maxN+1, i):
sieve[cur] = False

res = []
for i, val in enumerate(sieve):
if val:
res.append(i)
return res

[saikamireddi]

this is my approch
def closestPrimes(self, left: int, right: int) -> List[int]:
#brute force solution
def is_prime(num):
if num<2 or(num>2 and num%2==0):
return False
for i in range(3, int(math.sqrt(num))+1, 2):
if num%i==0:
return False
return True
prime_numbers=[]
max_diff=float('inf')
for n in range(left, right+1):
if is_prime(n):
prime_numbers.append(n)
if len(prime_numbers)==0 or len(prime_numbers)==1:
return [-1, -1]
else:
for i in range(1, len(prime_numbers)):

if diff<max_diff:
max_diff=diff
result=[prime_numbers[i-1], prime_numbers[i]]
return result