class Solution {
public:
bool primeSubOperation(vector<int>& nums) {
}
};
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 。
示例 2：
输入：nums = [6,8,11,12] 输出：true 解释：nums 从一开始就按严格递增顺序排序，因此不需要执行任何运算。
示例 3：
输入：nums = [5,8,3] 输出：false 解释：可以证明，执行运算无法使 nums 按严格递增顺序排序，因此答案是 false 。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1000nums.length == n原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2023-03-29 14:56:33
var p = []int{0} // 哨兵，避免二分越界
func init() {
const mx = 1000
np := [mx]bool{}
for i := 2; i < mx; i++ {
if !np[i] {
p = append(p, i) // 预处理质数列表
for j := i * i; j < mx; j += i {
np[j] = true
}
}
}
}
func primeSubOperation(nums []int) bool {
pre := 0
for _, x := range nums {
if x <= pre {
return false
}
pre = x - p[sort.SearchInts(p, x-pre)-1] // 减去 < x-pre 的最大质数
}
return true
}
java 解法, 执行用时: 2 ms, 内存消耗: 41.3 MB, 提交时间: 2023-03-29 14:56:12
class Solution {
private final static int MX = 1000;
private final static int[] primes = new int[169];
static {
var np = new boolean[MX + 1];
int pi = 1; // primes[0] = 0 避免二分越界
for (int i = 2; i <= MX; ++i)
if (!np[i]) {
primes[pi++] = i; // 预处理质数列表
for (int j = i; j <= MX / i; ++j)
np[i * j] = true;
}
}
public boolean primeSubOperation(int[] nums) {
int pre = 0;
for (int x : nums) {
if (x <= pre) return false;
int j = lowerBound(primes, x - pre);
pre = x - primes[j - 1];
}
return true;
}
// 见 https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(int[] nums, int target) {
int left = -1, right = nums.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid; // 范围缩小到 (mid, right)
else
right = mid; // 范围缩小到 (left, mid)
}
return right;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2023-03-29 14:54:25
'''
设 pre 是上一个减完后的数字，x = nums[i] 为当前数字。
设 p 是满足 x−p>pre 的最大质数，换言之，p 是小于 x−pre 的最大质数，这可以预处理质数列表后，用二分查找得到。
'''
MX = 1000
P = [0] # 哨兵，避免二分越界
is_prime = [True] * MX
for i in range(2, MX):
if is_prime[i]:
P.append(i) # 预处理质数列表
for j in range(i * i, MX, i):
is_prime[j] = False
class Solution:
def primeSubOperation(self, nums: List[int]) -> bool:
pre = 0
for x in nums:
if x <= pre: return False
pre = x - P[bisect_left(P, x - pre) - 1] # 减去 < x-pre 的最大质数
return True