2601. 質(zhì)數(shù)減法運算
給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，數(shù)組長度為 n 欲诺。
你可以執(zhí)行無限次下述運算：
選擇一個之前未選過的下標(biāo) i 渺鹦，并選擇一個 嚴(yán)格小于 nums[i] 的質(zhì)數(shù) p ，從 nums[i] 中減去 p 海铆。
如果你能通過上述運算使得 nums 成為嚴(yán)格遞增數(shù)組，則返回 true 殴边；否則返回 false 珍语。
嚴(yán)格遞增數(shù)組 中的每個元素都嚴(yán)格大于其前面的元素。
示例 1：
輸入：nums = [4,9,6,10]
輸出：true
解釋：
在第一次運算中：選擇 i = 0 和 p = 3 是偷，然后從 nums[0] 減去 3 ，nums 變?yōu)?[1,9,6,10] 蛋铆。
在第二次運算中：選擇 i = 1 和 p = 7 刺啦，然后從 nums[1] 減去 7 ，nums 變?yōu)?[1,2,6,10] 玛瘸。
第二次運算后，nums 按嚴(yán)格遞增順序排序右核，因此答案為 true 渺绒。
解題思路：第一個數(shù)減去和自己在值方面接近的最大質(zhì)數(shù)，后面的數(shù)依次進(jìn)行計算
#篩質(zhì)數(shù)的方法(0, 1既不是質(zhì)數(shù)也不是合數(shù))
MX = 1000 #1 <= nums.length <= 1000
is_prime = [True]*MX
primes = [0]
for i in range(2, MX):
#當(dāng)該數(shù)是質(zhì)數(shù)搜变，添加
if is_prime[i]:
primes.append(i)
#質(zhì)數(shù)的倍數(shù)(遍歷步長為i)不是質(zhì)數(shù)针炉，因此可以提前標(biāo)記(從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]的最大質(zhì)數(shù)的下標(biāo)
pre = nums[0] - primes[j]
for i in range(1, len(nums)):
x = nums[i]
# 當(dāng)前值已經(jīng)布滿條件扳抽，及時返回
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
