Code : Minimum Division Operations to Make Array Non Decreasing

bool precomputed = false;
const int maxn = (int)1e6 + 6;
vector<int> spf(maxn);
const int inf = 1e9;

void sieve() {
    if (precomputed) {
        return;
    }

    for (int i = 1; i < maxn; i++) {
        spf[i] = i;
    }

    for (int i = 2; i < maxn; i++) {
        // Process primes only.
        if (spf[i] != i) {
            continue;
        }
        for (int j = i; j < maxn; j += i) {
            // If it has not been marked yet, mark it.
            if (spf[j] == j) {
                spf[j] = i;
            }
        }
    }
    precomputed = true;
}

class Solution {
  public:
    int minOperations(vector<int> &nums);
};

int Solution::minOperations(vector<int> &a) {
    int n = a.size();
    sieve();

    map<int, int> dp;
    dp[0] = 0;
    // dp[ele] is the minimum number of operations required to make the array
    // increasing when the last element is 'ele'.
    for (int num : a) {
        map<int, int> opcount;
        opcount[num] = 0;

        int cnt = 0;
        while (num != spf[num]) {
            cnt++;
            num = spf[num];
            opcount[num] = cnt;
        }

        map<int, int> ndp;
        for (auto &[ele, _] : opcount) {
            ndp[ele] = inf;
        }
        for (auto &[lst, _] : dp) {
            for (auto &[nxt, __] : opcount) {
                if (nxt >= lst) {
                    ndp[nxt] = min(ndp[nxt], dp[lst] + opcount[nxt]);
                }
            }
        }
        swap(dp, ndp);
    }
    int res = inf;
    for (auto &[lst, _] : dp) {
        res = min(res, dp[lst]);
    }
    return (res < inf ? res : -1);
}

bool precomputed = false;
const int maxn = (int)1e6 + 6;
vector<int> spf(maxn);
const int inf = 1e9;

void sieve() {
    if (precomputed) {
        return;
    }

    for (int i = 1; i < maxn; i++) {
        spf[i] = i;
    }

    for (int i = 2; i < maxn; i++) {
        // Process primes only.
        if (spf[i] != i) {
            continue;
        }
        for (int j = i; j < maxn; j += i) {
            // If it has not been marked yet, mark it.
            if (spf[j] == j) {
                spf[j] = i;
            }
        }
    }
    precomputed = true;
}

class Solution {
  public:
    int minOperations(vector<int> &nums);
};

int Solution::minOperations(vector<int> &a) {
    int n = a.size();
    sieve();

    int lst = inf;
    int cost = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (a[i] > lst) {
            if (a[i] == spf[a[i]]) {
                return -1;
            }
            a[i] = spf[a[i]];
            cost++;
        }
        lst = a[i];
    }

    return cost;
}