Untitled

class Solution {
public:
    static int spf[1000001]; 
    
    Solution() {
        static bool init = false;
        if (!init) {
            sieve(1000000);
            init = true;
        }
    }
    
    static void sieve(int mx) {
        for (int i = 1; i <= mx; ++i) {
            spf[i] = i;
        }

        for (int i = 2; i * i <= mx; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= mx; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }

    // Function to get the greatest prime divisor (gpd)
    int gpd(int n) {
        return (n == 1 ? 1 : n / spf[n]);
    }

    int minOperations(vector<int>& nums) {
        int ans = 0, n = nums.size();

        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] > nums[i + 1]) {
                int div = gpd(nums[i]);
                if (nums[i] / div > nums[i + 1]) return -1;

                nums[i] = nums[i] / div;
                ans++;
            }
        }

        return ans;
    }
};

int Solution::spf[1000001];