Leetcode 3115 Maximum Prime Difference

3115. 质数的最大距离

[ 中等 ] -> 数组 数学 数论

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。

示例 1：

• 输入： nums = [4,2,9,5,3]
• 输出： 3
• 解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

• 输入： nums = [4,8,2,8]
• 输出： 0
• 解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

提示：

• 1 <= nums.length <= 3 * 10^5
• 1 <= nums[i] <= 100
• 输入保证 nums 中至少有一个质数。

Tip1: Find all prime numbers in the nums.

Tip2: Find the first and the last prime number in the nums.

解法一

质数判断：质数的因数只有1和它本身，所以用n除以2到$\sqrt{n}$来判断有无其他因数，进而判断是否为质数.

寻找质数位置：用一个列表来保存质数的下标，然后用$last-first$作为结果返回.

class Solution:
    def is_prime(self,n:int) -> bool:
        if n<2:
            return False
        else:
            for i in range (2,int(sqrt(n))+1):
            #这里一开始忘记给上界+1了，会导致(2,2)没有包含2
                if n%i == 0:
                    return False
            return True
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        list=[]
        for i in range(len(nums)):
            if self.is_prime(nums[i]):
                list.append(i)
        return list[-1]-list[0]

解法二：筛质数

@灵茶山艾府 力扣（LeetCode）

注意标记 i 的倍数时，只需从 $ j = i^2 $ 开始，因为小于 $ i^2 $ 的合数（非质数） $ j $ 一定有一个小于 $ i $ 的质因子。可以用反证法证明：如果小于 $ i^2 $ 的合数 $ j $ 没有小于 $ i $ 的质因子，那么合数 $ j $ 至少是两个 $ \geq i $ 的数的乘积，这与 $ j < i^2 $ 矛盾。

# 默认0-100共101个数标记为质数（非质数为false）
not_prime = [False] * 101
# 1不是质数
not_prime[1] = True
# 2,3,5,7是质数，那么从他们的平方到上限值100的范围内，他们自身的整数倍都不是质数
# 2： 从 4 - 100 除去所有的2 的倍数
# 3： 从 9 - 100 除去所有的3 的倍数
# 5： 从 25 - 100 除去所有的5 的倍数
# 7： 从 49 - 100 除去所有的7 的倍数
for i in 2, 3, 5, 7:
    for j in range(i * i, 101, i):
        not_prime[j] = True

class Solution:
    #从前向后找第一个，从后向前找最后一个
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        i = 0
        while not_prime[nums[i]]:
            i += 1
        j = len(nums) - 1
        while not_prime[nums[j]]:
            j -= 1
        return j - i

解法三：位运算

@灵茶山艾府 力扣（LeetCode）

把 100 内的质数组成的集合，「压缩」成两个 64 位整数。（Python 只需要一个 int）

class Solution:
    def maximumPrimeDifference(self, nums: List[int]) -> int:
        PRIME_MASK = 0x20208828828208a20a08a28ac
        i = 0
        while PRIME_MASK >> nums[i] & 1 == 0:
            i += 1
        j = len(nums) - 1
        while PRIME_MASK >> nums[j] & 1 == 0:
            j -= 1
        return j - i