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.
  • nums1 and nums2 are both prime numbers.
  • nums2 - nums1 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 minimum nums1 value or [-1, -1] if such numbers do not exist.
    A number greater than 1 is called prime if it is only divisible by 1 and 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

二、分析

三、解題

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;
}

回目錄 Catalog