Advertisement
am1x

cpnir001

Mar 9th, 2025
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.18 KB | Fixit | 0 0
  1. import bisect
  2. N = 1000000
  3.  
  4. def gen_primes(n):
  5.     m = (n + 1) // 2
  6.     s = [1] * m
  7.     for i in range(1, m):
  8.         if s[i]:
  9.             j0 = 2 * i * (i + 1)
  10.             if (m <= j0):
  11.                 break
  12.             for j in range(j0, m, 2 * i + 1):
  13.                 s[j] = 0
  14.     ps = []
  15.     if (2 <= n):
  16.         ps.append(2)
  17.     for i in range(1, m):
  18.         if s[i]:
  19.             ps.append(2 * i + 1)
  20.     return ps
  21.  
  22. ps = gen_primes(N)
  23.  
  24. class Solution:
  25.     def closestPrimes(self, l: int, r: int) -> List[int]:
  26.         assert (l <= r)
  27.         if l <= 2:
  28.             if r >= 3:
  29.                 return [2, 3]
  30.             else:
  31.                 return [-1, -1]
  32.        
  33.         i0 = bisect.bisect_left(ps, l)
  34.         if (i0 + 1 >= len(ps)) or ps[i0 + 1] > r:
  35.             return [-1, -1]
  36.         resi = i0 + 1
  37.         resd = ps[resi] - ps[resi - 1]
  38.         for i in range(i0 + 2, len(ps)):
  39.             if (resd <= 2):
  40.                 break
  41.             pi = ps[i]
  42.             if pi > r:
  43.                 break
  44.             pid = pi - ps[i - 1]
  45.             if pid < resd:
  46.                 resi = i
  47.                 resd = pid
  48.         return [ps[resi - 1], ps[resi]]
  49.  
Tags: leetcode
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement