1.题目基本信息

1.1.题目描述

给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。

你可以执行无限次下述运算：

• 选择一个之前未选过的下标 i ，并选择一个 严格小于 nums[i] 的质数 p ，从 nums[i] 中减去 p 。

如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。

严格递增数组 中的每个元素都严格大于其前面的元素。

1.2.题目地址

https://leetcode.cn/problems/prime-subtraction-operation/description/

2.解题方法

2.1.解题思路

线性筛/埃氏筛 + 二分查找

2.2.解题步骤

第一步，使用质数筛找到1000以内的所有质数，得到primes数组，此时的primes数组中元素是升序的

第二步，遍历nums，记遍历索引为i，记前一项修改后的值为prev，则需要找到最大的质数prime，使nums[i]-prime>prev，即从primes中找到小于nums[i]-prev的最大质数，由于primes中元素升序，所以可以采用二分查找进行；如果出现找不到的情况，则说明没法通过若干操作达到题目中要求

• 2.1.红蓝染色。左开右开。红色区域：始终小于nums[i]-prev的区域，蓝色区域：始终大于等于nums[i]-prev的区域。left始终指向红色区域，right始终指向蓝色区域。最终的left指针就是要找的位置

3.解题代码

python代码

class Solution:
    # 线性筛获取质数列表
    def getPrimes(self):
        primes = []
        isPrime = [1] * 1001
        for i in range(2, 1001):
            if isPrime[i]:
                primes.append(i)
            for prime in primes:
                if prime * i < 1001:
                    isPrime[prime * i] = 0
                else:
                    break
                if i % prime == 0:
                    break
        return primes

    # 埃氏筛获取质数列表
    def getPrimes2(self):
        primes = []
        isPrime = [1] * 1001
        for i in range(2, 1001):
            if not isPrime[i]:
                continue
            primes.append(i)
            j = i
            while i * j < 1001:
                isPrime[i * j] = 0
                j += 1
        return primes

    def primeSubOperation(self, nums: List[int]) -> bool:
        # 思路1：质数筛+二分查找
        n = len(nums)
        # 第一步，使用质数筛找到1000以内的所有质数，得到primes数组，此时的primes数组中元素是升序的
        primes = self.getPrimes()  # 埃氏筛
        # primes = self.getPrimes2()  # 埃氏筛
        # print(primes)
        # 第二步，遍历nums，记遍历索引为i，记前一项修改后的值为prev，则需要找到最大的质数prime，使nums[i]-prime>prev，即从primes中找到小于nums[i]-prev的最大质数，由于primes中元素升序，所以可以采用二分查找进行；如果出现找不到的情况，则说明没法通过若干操作达到题目中要求
        primes = [0] + primes
        prev = 0
        for i in range(n):
            # 2.1.红蓝染色。左开右开。红色区域：始终小于nums[i]-prev的区域，蓝色区域：始终大于等于nums[i]-prev的区域。left始终指向红色区域，right始终指向蓝色区域。最终的left指针就是要找的位置
            left, right = -1, len(primes)
            while left + 1 < right:
                mid = (right - left) // 2 + left
                if primes[mid] < nums[i] - prev:
                    left = mid
                else:
                    right = mid
            if not (0 <= left < len(primes)):
                return False
            prev = nums[i] - primes[left]
            # print(left, primes[left])
        return True

4.执行结果