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
