Minimum Division Operations to Make Array Non Decreasing
<p>You are given an integer array <code>nums</code>.</p>

<p>Any <strong>positive</strong> divisor of a natural number <code>x</code> that is <strong>strictly less</strong> than <code>x</code> is called a <strong>proper divisor</strong> of <code>x</code>. For example, 2 is a <em>proper divisor</em> of 4, while 6 is not a <em>proper divisor</em> of 6.</p>

<p>You are allowed to perform an <strong>operation</strong> any number of times on <code>nums</code>, where in each <strong>operation</strong> you select any <em>one</em> element from <code>nums</code> and divide it by its <strong>greatest</strong> <strong>proper divisor</strong>.</p>

<p>Return the <strong>minimum</strong> number of <strong>operations</strong> required to make the array <strong>non-decreasing</strong>.</p>

<p>If it is <strong>not</strong> possible to make the array <em>non-decreasing</em> using any number of operations, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [25,7]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p>Using a single operation, 25 gets divided by 5 and <code>nums</code> becomes <code>[5, 7]</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [7,7,6]</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>
Greedy; Array; Math; Number Theory
const int MX = 1e6;
int LPF[MX + 1];

auto init = [] {
    for (int i = 2; i <= MX; i++) {
        if (LPF[i] == 0) {
            for (int j = i; j <= MX; j += i) {
                if (LPF[j] == 0) {
                    LPF[j] = i;
                }
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) {
                nums[i] = LPF[nums[i]];
                if (nums[i] > nums[i + 1]) {
                    return -1;
                }
                ans++;
            }
        }
        return ans;
    }
};
