aboutsummaryrefslogtreecommitdiff
path: root/closest_prime_num_range.py
diff options
context:
space:
mode:
Diffstat (limited to 'closest_prime_num_range.py')
-rw-r--r--closest_prime_num_range.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/closest_prime_num_range.py b/closest_prime_num_range.py
new file mode 100644
index 0000000..d4ab237
--- /dev/null
+++ b/closest_prime_num_range.py
@@ -0,0 +1,43 @@
+# 2523. Closest Prime Numbers in Range
+
+"""
+given two positive integers 'left' and 'right', find the two integers 'num1'
+and 'num2' such that 'left <= num1 < num2 <= right', both 'num1' and 'num2'
+are prime numbers, and 'num2 - num1' is the minimum amongst all other pairs
+satisfying the above conditions. return the positive integer array 'ans =
+[nums1, nums2]'. if there are multiple pairs satisfying these conditions,
+return the one with the smallest 'num1' value. if no such numbers exist,
+return '[-1, -1]'.
+"""
+
+
+class Solution(object):
+ def closestPrimes(self, left, right):
+ """
+ :type left: int
+ :type right: int
+ :rtype: List[int]
+ """
+ sieve = [True] * (right + 1)
+ sieve[0] = sieve[1] = False
+ for i in range(2, int(right**0.5) + 1):
+ if sieve[i]:
+ for j in range(i * i, right + 1, i):
+ sieve[j] = False
+ primes = [i for i in range(left, right + 1) if sieve[i]]
+ if len(primes) < 2:
+ return [-1, -1]
+ min = float("inf")
+ ans = [-1, -1]
+ for i in range(1, len(primes)):
+ gap = primes[i] - primes[i - 1]
+ if gap < min:
+ min = gap
+ ans = [primes[i - 1], primes[i]]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.closestPrimes(left=10, right=19))
+ print(obj.closestPrimes(left=4, right=6))