題目資訊

題目編號: 2523
題目連結: Closest Prime Numbers in Range
主題: Math, Number Theory

題目敘述

給定兩個正整數 left 和 right，找出兩個整數 num1 和 num2，使得：

$left \leq num1 < num2 \leq right$。
num1 和 num2 都是質數。
$num2 - num1$ 是滿足上述條件的所有其他對中最小的。

返回正整數數組 $ans = [num1, num2]$。如果有多個對滿足這些條件，返回其中 num1 值最小的。如果不存在這樣的數，返回 $[-1, -1]$。

範例 1:

輸入: left = 10, right = 19
輸出: [11,13]
解釋: 10 到 19 之間的質數是 11、13、17 和 19。
任何一對之間的最小間距是 2，可以通過 [11,13] 或 [17,19] 實現。
由於 11 比 17 小，我們返回第一對。

範例 2:

輸入: left = 4, right = 6
輸出: [-1,-1]
解釋: 在給定範圍內只有一個質數存在，因此無法滿足條件。

約束條件:

$1 \leq left \leq right \leq 10^6$

直覺

此問題要求在給定範圍內找到兩個質數，使它們之間的差值最小。這暗示我們需要遍歷該範圍內的數字並檢查每個數字是否為質數。為了實現最小差異，一旦識別出兩個連續的質數，就應該將它們與任何已有的最近配對進行比較，以確定它們是否距離更近。

解法

解決這個問題的根本方法是從 left 邊界到 right 邊界迭代，檢查每個數字是否為質數，然後維護找到的兩個最近質數的記錄。詳細步驟如下：

質數檢查函數：
- 使用輔助函數 is_prime 來確定一個數字是否為質數。
- 該函數通過對小於2的數字返回 false，以及直接對2和3返回 true 來處理邊界情況。
- 對於大於3的數字，立即消除偶數和3的倍數以減少不必要的計算。
- 對於其他數字，從5開始檢查其可整除性，直到數字的平方根，以6為增量，因為5和7是跳過小質數（2和3）的倍數後的第一個非倍數。
遍歷範圍：
- 初始化變量 previousPrime 以存儲最近找到的質數，result 用來存儲找到的最近質數對。起初，兩者均設置為表示尚未找到有效質數的值（-1）。
識別最近的質數：
- 遍歷從 left 到 right 的每一個整數。
- 對於每個整數，使用 is_prime 函數來判定是否為質數。
- 如果找到一個質數，檢查其與 previousPrime 所形成的差值是否比 result 中先前記錄的任一對的差值更小。
- 如果找到更近的配對，則用新的一對質數更新 result。
- 更新 previousPrime 為當前的質數。
返回結果：
- 完成迭代後，返回 result，其中包含最近的質數對，或者在未找到有效對的情況下返回 [-1, -1]。

這種方法確保了解決方案的高效性，並且通過最小化非質數的運算，僅關注潛在的質數候選，從而尊重了約束條件。此外，它還通過僅在必要時更新結果以保證最小的 num1 優先級。

程式碼

C++

class Solution {
public:
    // 檢查一個數字是否為質數
    bool is_prime(int n) {
        if (n < 2) return false; // 小於2的數字不是質數
        if (n == 2 || n == 3) return true; // 2和3是質數
        if (n % 2 == 0 || n % 3 == 0) return false; // 排除2和3的倍數

        // 從5開始檢查n的因數
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }

    // 尋找在left和right之間最接近的質數
    vector<int> closestPrimes(int left, int right) {
        int previousPrime = -1; // 儲存最後找到的質數
        vector<int> result = {-1, -1}; // 儲存最接近的質數對

        for (int i = left; i <= right; i++) {
            if (is_prime(i)) {
                // 檢查當前質數和前一個質數是否比當前結果更接近
                if (previousPrime != -1 && (result[0] == -1 || i - previousPrime < result[1] - result[0])) {
                    result = {previousPrime, i}; // 使用新的最接近對更新結果
                }
                previousPrime = i; // 更新前一個質數為當前質數
            }
        }
        
        return result;
    }
};

Python

class Solution:
    # 檢查一個數是否為質數
    def is_prime(self, n: int) -> bool:
        if n < 2:
            return False  # 小於 2 的數字不是質數
        if n == 2 or n == 3:
            return True  # 2 和 3 是質數
        if n % 2 == 0 or n % 3 == 0:
            return False  # 排除 2 和 3 的倍數

        # 檢查 n 的因數，從 5 開始
        for i in range(5, int(n**0.5) + 1, 6):
            if n % i == 0 or n % (i + 2) == 0:
                return False
        return True

    # 找出位於 left 和 right 之間最接近的質數
    def closestPrimes(self, left: int, right: int) -> list[int]:
        previousPrime = -1  # 儲存最後找到的質數
        result = [-1, -1]  # 儲存最接近的質數對

        for i in range(left, right + 1):
            if self.is_prime(i):
                # 檢查當前質數與前一個質數是否比目前結果更接近
                if previousPrime != -1 and (result[0] == -1 or i - previousPrime < result[1] - result[0]):
                    result = [previousPrime, i]  # 使用新的最接近對更新結果
                previousPrime = i  # 更新前一個質數為當前質數

        return result

複雜度分析

時間複雜度: 整體時間複雜度為 $O(n \sqrt{m})$，其中 $n$ 為 right 和 left 的差異 ($n = \text{right} - \text{left} + 1$)，而 $m$ 是範圍內的最大數字，實質上即為 right。原因在於對於每個 left 和 right 之間的數字，都會調用 is_prime 函數，該函數的時間複雜度為 $O(\sqrt{m})$，因為要檢查可能的除數直到該數字的平方根為止。
空間複雜度: 空間複雜度為 $O(1)$。此演算法使用固定數量的空間來儲存如 previousPrime 和 result 等變數，不需要其他隨著輸入大小而變化的額外空間。

CS Note
En

Leetcode 2523. Closest Prime Numbers in Range

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析