范围内最接近的两个质数

难度: Medium

给你两个正整数 left 和 right ，请你找到两个整数 num1 和 num2 ，它们满足：

left <= nums1 < nums2 <= right 。
nums1 和 nums2 都是质数。
nums2 - nums1 是满足上述条件的质数对中的 最小值 。

请你返回正整数数组 ans = [nums1, nums2] 。如果有多个整数对满足上述条件，请你返回 nums1 最小的质数对。如果不存在符合题意的质数对，请你返回 [-1, -1] 。

如果一个整数大于 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 <= left <= right <= 10⁶

Submission

运行时间: 25 ms

内存: 16.1 MB

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        def zhishu(n : int) -> bool:
            if n < 2 : return False
            if n == 2 : return True
            if n % 2 == 0 : return False
            seed = [2, 3, 5] # ,7,11,13,17,19]
            s = 0
            now = n-1
            while now % 2 == 0 :
                s += 1
                now = now // 2
            d = now
            for a in seed:
                if a < n:
                    x = pow(a, d, n)
                    for i in range(s):
                        y = pow(x, 2, n)
                        if y == 1 and x != 1 and x != n-1:
                            return False
                        x = y
                    if y != 1 : return False
            return True

        now = -1
        result1 = -1
        result2 = -1
        diff = -1
        for v in range(left, right + 1):
            if zhishu(v):
                if now > 0 :
                    if diff > 0 and v - now < diff :
                        result1 = now
                        result2 = v
                        diff = v - now
                    elif diff <= 0 :
                        result1 = now
                        result2 = v
                        diff = v - now
                now = v
            if diff == 1:
                return [result1, result2]
            if diff == 2:
                return [result1, result2]
        return [result1, result2]

Explain

这道题目的目标是在给定的范围内找到差值最小的质数对。首先，我们需要一个有效的方法来判断一个数是否是质数。这里使用了一个基于Miller-Rabin素性测试的方法，这是一个概率性质数测试，用于判断大整数是否是质数。在给定区间内，我们遍历每个数，使用素性测试函数判断是否是质数。如果是，我们比较这个质数和上一个找到的质数的差值，如果比当前记录的最小差值小，我们更新结果。最后，如果找到至少一对质数，返回差值最小的那对；否则，返回[-1, -1]。这个方法依靠逐个检查每个数是否为质数，并记录最小差值，直到遍历完整个区间。

时间复杂度: O((right-left+1)*log^3(right))

空间复杂度: O(1)

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        def zhishu(n : int) -> bool:
            if n < 2 : return False
            if n == 2 : return True
            if n % 2 == 0 : return False
            seed = [2, 3, 5]  # 使用基数进行素性测试
            s = 0
            now = n-1
            while now % 2 == 0 :  # 找到n-1的最大偶数因子
                s += 1
                now = now // 2
            d = now
            for a in seed:
                if a < n:
                    x = pow(a, d, n)
                    for i in range(s):
                        y = pow(x, 2, n)
                        if y == 1 and x != 1 and x != n-1:
                            return False
                        x = y
                    if y != 1 : return False
            return True

        now = -1
        result1 = -1
        result2 = -1
        diff = -1
        for v in range(left, right + 1):
            if zhishu(v):
                if now > 0 :
                    if diff > 0 and v - now < diff :
                        result1 = now
                        result2 = v
                        diff = v - now
                    elif diff <= 0 :
                        result1 = now
                        result2 = v
                        diff = v - now
                now = v
            if diff == 1:
                return [result1, result2]
            if diff == 2:
                return [result1, result2]
        return [result1, result2]  # 返回最接近的质数对或[-1, -1]

Explore

Miller-Rabin素性测试是一种概率性测试，通过选择一些基数来测试一个数是否为质数。选择[2, 3, 5]作为基数是因为它们是最小的三个质数，能够比较有效地覆盖较小范围内的数的测试。对于较大的数，这三个基数并不能完全保证测试的准确性，但对于一般的编程挑战或较小的数范围，这些基数通常足以提供可接受的准确度和效率。在实际应用中，如果需要更高的证实力，可以增加更多的基数进行测试。

在这个算法中，如果left和right相等，算法会检查这个单一值是否为质数。如果是，由于没有其他质数与之比较，结果会返回 [-1, -1]。如果left和right之间没有质数，同样由于没有质数对可以比较，结果也会返回 [-1, -1]。这种处理方法确保了算法能够处理包括没有质数或只有单一质数的边界情况。

在Miller-Rabin素性测试中，首先将n-1表示为2^s * d的形式，其中d是奇数。然后选择一个基数a，并计算x = a^d % n。如果x为1或n-1，则认为n可能是质数。接着，对x进行连续平方，计算y = x^2 % n。如果在过程中y等于1而x不等于1或n-1，这表明n不是质数。如果x的连续平方最终变为n-1，则继续认为n可能是质数。这个循环确保了n不是合数的强证据，因为对于真合数n，按照费马小定理和其扩展，这种情况概率很低。