diff options
-rw-r--r-- | closest_prime_num_range.c | 61 | ||||
-rw-r--r-- | closest_prime_num_range.py | 43 |
2 files changed, 104 insertions, 0 deletions
diff --git a/closest_prime_num_range.c b/closest_prime_num_range.c new file mode 100644 index 0000000..673ab00 --- /dev/null +++ b/closest_prime_num_range.c @@ -0,0 +1,61 @@ +// 2523. Closest Prime Numbers in Range +#include "leetcode.h" + +/* + * 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]'. + */ + +int *closestPrimes(int left, int right, int *returnSize) { + int *ans = (int *)malloc(2 * sizeof(int)); + *returnSize = 2; + ans[0] = -1; + ans[1] = -1; + + bool *sieve = (bool *)malloc((right + 1) * sizeof(bool)); + memset(sieve, true, (right + 1) * sizeof(bool)); + sieve[0] = sieve[1] = false; + for (int i = 2; i * i <= right; i++) + if (sieve[i]) + for (int j = i * i; j <= right; j += i) + sieve[j] = false; + int *prime = (int *)malloc((right - left + 1) * sizeof(int)); + int idx = 0; + for (int i = left; i <= right; i++) + if (sieve[i]) + prime[idx++] = i; + free(sieve); + if (idx < 2) { + free(prime); + return ans; + } + int min = INT_MAX; + for (int i = 1; i < idx; i++) { + int diff = prime[i] - prime[i - 1]; + if (min > diff) { + min = diff; + ans[0] = prime[i - 1]; + ans[1] = prime[i]; + } + } + free(prime); + return ans; +} + +int main() { + int rs1, *cp1 = closestPrimes(10, 19, &rs1); + int rs2, *cp2 = closestPrimes(4, 6, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", cp1[i]); // expect: 11 13 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", cp2[i]); // expect: -1 -1 + printf("\n"); + free(cp1); + free(cp2); +} 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)) |