LeetCode每日一题：质数运算

2601. 质数减法运算

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。
你可以执行无限次下述运算：
选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。
如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。
严格递增数组 中的每个元素都严格大于其前面的元素。

示例 1：
输入：nums = [4,9,6,10]
输出：true
解释：
在第一次运算中：选择 i = 0 和 p = 3 ，然后从 nums[0] 减去 3 ，nums 变为 [1,9,6,10] 。
在第二次运算中：选择 i = 1 和 p = 7 ，然后从 nums[1] 减去 7 ，nums 变为 [1,2,6,10] 。
第二次运算后，nums 按严格递增顺序排序，因此答案为 true 。

解题思路：第一个数减去和自己在值方面接近的最大质数，后面的数依次进行计算

#筛质数的方法(0, 1既不是质数也不是合数)
MX = 1000    #1 <= nums.length <= 1000
is_prime = [True]*MX
primes = [0]
for i in range(2, MX):
    #当该数是质数，添加
    if is_prime[i]:
        primes.append(i)
        #质数的倍数(遍历步长为i)不是质数，因此可以提前标记(从i^2开始计算)
        for j in range(i*i, MX, i):
            is_prime[j] = False

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        j = bisect_left(primes, nums[0]) - 1    #找到小于nums[0]的最大质数的下标
        pre = nums[0] - primes[j]
        for i in range(1, len(nums)):
            x = nums[i]
            # 当前值已经布满条件，及时返回
            if x <= pre:
                return False
            # 剩下的每个元素都需要满足的条件
            # x - primes[j] > pre  ==> primes[j] < x - pre
            j = bisect_left(primes, x - pre) - 1
            pre = x - primes[j]
        return True