题目描述

给你一个整数数组 nums。

一个正整数 x 的任何一个 严格小于 x 的 正 因子都被称为 x 的 真因数。比方说 2 是 4 的 真因数，但 6 不是 6 的 真因数。

你可以对 nums 的任何数字做任意次 操作，一次 操作 中，你可以选择 nums 中的任意一个元素，将它除以它的 最大真因数。

你的目标是将数组变为 非递减 的，请你返回达成这一目标需要的 最少操作 次数。

如果 无法 将数组变成非递减的，请你返回 -1。

样例

输入：nums = [25,7]

输出：1

解释：

通过一次操作，25 除以 5，nums 变为 [5, 7]。

输入：nums = [7,7,6]

输出：-1

输入：nums = [1,1,1,1]

输出：0

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

算法

(线性筛) $O(n + m)$

1. 通过线性筛找到每个数字的最大真因数。由于线性筛是通过每个数字的最小质因数筛去的，所以可以顺便找到最大的真因数。
2. 倒序遍历原数组，如果当前数字比后一个数字要大，则除以真因数再次判定。

时间复杂度

• 线性筛的时间复杂度为 $O(m)$。
• 注意到，每个数字最多操作一次，且操作后就变为了质数。
• 故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(m)$ 的额外空间存储线性筛的结果。

C++ 代码

const int N = 1000010;

int prime[N], cnt;
bool is_not_prime[N];
int fac[N];

auto init = []{
    for (int i = 2; i < N; i++) {
        if (!is_not_prime[i])
            prime[cnt++] = i;

        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            is_not_prime[i * prime[j]] = true;
            fac[i * prime[j]] = i;
            if (i % prime[j] == 0)
                break;
        }
    }

    return 0;
}();

class Solution {
public:
    int minOperations(vector<int>& nums) {
        const int n = nums.size();

        int ans = 0;
        for (int i = n - 2; i >= 0; i--) {
            while (nums[i] > nums[i + 1]) {
                if (!is_not_prime[nums[i]])
                    return -1;

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

        return ans;
    }
};