2601. Prime Subtraction Operation

You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

• Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].

Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

class Solution {
    int sieve[1010];
    vector<int> prime() {
        vector<int> res;
        for(int i = 2; i < 1000; i++) {
            if(sieve[i]) continue;
            res.push_back(i);
            for(int j = i * i; j < 1000; j += i) {
                sieve[j] = true;
            }
        }
        return res;
    }
public:
    bool primeSubOperation(vector<int>& A) {
        vector<int> p = prime();
        int last = -1000;
        for(int i = 0; i < A.size(); i++) {
            auto pos = lower_bound(begin(p), end(p), A[i]) - begin(p) - 1;
            while(pos >= 0 and A[i] - p[pos] <= last) pos -= 1;
            if(pos == -1 and A[i] <= last) return false;
            last = A[i] - (pos >= 0 ? p[pos] : 0);
        }
        return true;
    }
};