Untitled

class Solution {
public:
    
    int spf[1000001];
    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;
                    }
                }
            }
        }
    }
    
    int gpd(int n){
        return (n == 1 ? 1 : n/spf[n]);
    }
    int minOperations(vector<int>& nums) {
        int ans = 0, n = nums.size();
        // spf.resize(1e6+2);
        sieve(1e6);
        // for(int i=0; i<1e6; ++i){
        //     cout<<spf[i]<<" ";
        // }
        
        // cout<<gpd(9)<<endl;
        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;
    }
};