Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import bisect
- N = 1000000
- def gen_primes(n):
- m = (n + 1) // 2
- s = [1] * m
- for i in range(1, m):
- if s[i]:
- j0 = 2 * i * (i + 1)
- if (m <= j0):
- break
- for j in range(j0, m, 2 * i + 1):
- s[j] = 0
- ps = []
- if (2 <= n):
- ps.append(2)
- for i in range(1, m):
- if s[i]:
- ps.append(2 * i + 1)
- return ps
- ps = gen_primes(N)
- class Solution:
- def closestPrimes(self, l: int, r: int) -> List[int]:
- assert (l <= r)
- if l <= 2:
- if r >= 3:
- return [2, 3]
- else:
- return [-1, -1]
- i0 = bisect.bisect_left(ps, l)
- if (i0 + 1 >= len(ps)) or ps[i0 + 1] > r:
- return [-1, -1]
- resi = i0 + 1
- resd = ps[resi] - ps[resi - 1]
- for i in range(i0 + 2, len(ps)):
- if (resd <= 2):
- break
- pi = ps[i]
- if pi > r:
- break
- pid = pi - ps[i - 1]
- if pid < resd:
- resi = i
- resd = pid
- return [ps[resi - 1], ps[resi]]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement