2601.质数减法运算

链接：2601.质数减法运算
难度：Medium
标签：贪心、数组、数学、二分查找、数论
简介：给你一个下标从 0 开始的整数数组 nums ，数组长度为 n 。如果你能通过上述运算使得 nums 成为严格递增数组，则返回 true ；否则返回 false 。

题解 1 - cpp

• 编辑时间：2023-03-26
• 执行用时：16ms
• 内存消耗：23MB
• 编程语言：cpp
• 解法介绍：线性筛后对每个数尝试尽可能取最小。

class Solution {
public:
    int primes[1005] = {0};
    bool primeSubOperation(vector<int>& nums) {
        getPrimes();
        nums[0] = formatNum(nums[0], 0);
        for (int i = 1; i < nums.size(); i++) {
            nums[i] = formatNum(nums[i], nums[i - 1]);
            if (nums[i] <= nums[i - 1]) return false;
        }
        return true;
    }
    int formatNum(int num, int prev) {
        int cur = num;
        for (int i = 1; i < primes[0] + 1 && primes[i] < num && num - primes[i] > prev; i++) {
            cur = min(cur, num - primes[i]);
        }
        return cur;
    }
    
    void getPrimes() {
        for (int i = 2; i < 1005; i++) {
            if (primes[i] == 0) primes[++primes[0]] = i;
            for (int j = 1; j <= primes[0] && i * primes[j] < 1005; j++) {
                primes[i * primes[j]] = 1;
                if (i % primes[j] == 0) break;
            }
        }
    }
};

题解 2 - python

• 编辑时间：2023-03-26
• 执行用时：364ms
• 内存消耗：15MB
• 编程语言：python
• 解法介绍：同上。

def getPrimes(nmax: int):
    primes = [0] * nmax
    for i in range(2, nmax):
        if primes[i] == 0:
            primes[0] += 1
            primes[primes[0]] = i
        for j in range(1, nmax):
            if i * primes[j] >= nmax:
                break
            primes[i * primes[j]] = 1
            if i % primes[j] == 0:
                break
    return primes
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        primes = getPrimes(1005)
        def formatNum(num: int, prev: int):
            cur = num
            for i in range(1, primes[0] + 1):
                if primes[i] >= num or num - primes[i] <= prev:
                    break
                cur = min(cur, num - primes[i])
            return cur
        nums[0] = formatNum(nums[0], 0)
        for i in range(1, len(nums)):
            nums[i] = formatNum(nums[i], nums[i-1])
            if nums[i] <= nums[i-1]:
                return False
        return True

题解 3 - rust

• 编辑时间：2023-03-26
• 执行用时：8ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

fn get_primes(max: usize) -> Vec<usize> {
    let mut primes = vec![0; max];
    for i in 2..max {
        if primes[i] == 0 {
            primes[0] += 1;
            let idx = primes[0];
            primes[idx] = i;
        }
        for j in 1..=primes[0] {
            let idx = i * primes[j];
            if idx >= max {
                break;
            }
            primes[idx] = 1;
            if i % primes[j] == 0 {
                break;
            }
        }
    }
    primes
}
impl Solution {
    pub fn prime_sub_operation(mut nums: Vec<i32>) -> bool {
        let primes = get_primes(1005);
        let format_num = |num: i32, prev: i32| {
            let mut cur = num;
            for i in 1..=primes[0] {
                if primes[i] as i32 >= num || num - primes[i] as i32 <= prev {
                    break;
                }
                cur = cur.min(num - primes[i] as i32);
            }
            cur
        };
        nums[0] = format_num(nums[0], 0);
        for i in 1..nums.len() {
            nums[i] = format_num(nums[i], nums[i - 1]);
            if nums[i] <= nums[i - 1] {
                return false;
            }
        }
        return true;
    }
}