2523. Closest Prime Numbers in Range
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
- \(\color{blue}\textsf{Weekly Contest 323}\)
一、題目
Given two positive integers left and right, find the two integers num1 and num2 such that:
left <= nums1 < nums2 <= right.nums1andnums2are both prime numbers.nums2 - nums1is the minimum amongst all other pairs satisfying the above conditions.
Return the positive integer arrayans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimumnums1value or[-1, -1]if such numbers do not exist.
A number greater than1is called prime if it is only divisible by1and itself.
Example 1:
- Input: left = 10, right = 19
- Output: [11,13]
- Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.
Example 2:
- Input: left = 4, right = 6
- Output: [-1,-1]
- Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.
Constraints:
1 <= left <= right <= 10^6
二、分析
- 這題基本上也是在實作
prime的pre-built table，所以我們就大方的借用 [2521. Distinct Prime Factors of Product of Array] 的 prime table 吧。
- 再來就是依序求質數中符合範圍且距離最小的兩個質數。
三、解題
1. Sieve of Eratosthenes
- Time complexity: \(O((R-L)\sqrt{R}/\log R)\)
- Space complexity: \(O((R-L)/\log R)\)
vector<int> closestPrimes(int left, int right) {
// create pre-built table
vector<int> table(right+1, 0);
iota(table.begin(), table.end(), 0);
table[1] = 0;
for (int i = 2; i <= right; i++) {
if (table[i] != i) continue;
for (int j = 2*i; j <= right; j += i) {
table[j] = i;
}
}
// 遍歷完所有符圍中的質數，回傳距離最小的兩個質數
stack<int> st;
int diff = INT_MAX;
vector<int> res = {-1,-1};
for (int i = left; i <= right; i++) {
if (table[i] != i) continue;
if (!st.empty()) {
if (i - st.top() < diff) {
diff = i - st.top();
res[0] = st.top();
res[1] = i;
}
}
st.push(i);
}
return res;
}