2025-05-17：使数组非递减的最少除法操作次数。用go语言，给定一个整数数组 nums。

定义：对于一个正整数 x，所有严格小于 x 的正因子称为 x 的“真因数”。举例来说，2 是 4 的真因数，但对于 6 来说，6 本身则不是它的真因数。

你可以对数组中的元素进行多次操作。每次操作中，选择数组中的某个元素，将它除以该元素的最大真因数。

目标是通过若干次操作，使得最终数组元素按照非递减顺序排列。

请你计算完成此目标所需的最少操作次数，如果无法实现，请返回 -1。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000。

输入：nums = [25,7]。

输出：1。

解释：

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

题目来自3226。

分步骤描述过程：

1. 预处理最小质因数（LPF）数组：

   • 初始化一个大小为1,000,001的数组lpf，用于存储每个数的最小质因数（Least Prime Factor）。
   • 遍历从2到1,000,000的每个数i：
     • 如果lpf[i]为0，说明i是质数。
     • 对于每个质数i，遍历其所有倍数j（即j = i, 2i, 3i, ...），如果lpf[j]尚未被赋值，则将其设为i。这样lpf[j]就是j的最小质因数。
   • 预处理完成后，lpf[x]表示x的最小质因数。例如，lpf[25] = 5，lpf[7] = 7。

2. 处理数组nums：

   • 从数组的倒数第二个元素开始向前遍历（即从右向左遍历）：
     • 对于当前元素nums[i]，如果它比后一个元素nums[i+1]大，则需要通过操作将其减小到不超过nums[i+1]。
     • 操作的定义是将nums[i]除以其最大真因数。最大真因数可以通过nums[i] / lpf[nums[i]]得到（因为nums[i]的最小质因数lpf[nums[i]]对应其最小真因数，而最大真因数是nums[i] / lpf[nums[i]]）。
     • 执行操作：nums[i] = lpf[nums[i]]（即nums[i]被替换为其最小质因数）。
     • 操作次数ans加1。
     • 如果操作后的nums[i]仍然大于nums[i+1]，则无法使数组非递减，直接返回-1。
   • 如果遍历完成后没有无法满足非递减的情况，返回操作次数ans。

3. 示例分析：

   • 输入nums = [25, 7]：
     • 从i = 0开始（因为数组长度为2，i从len(nums)-2=0开始）。
     • nums[0] = 25比nums[1] = 7大，需要进行操作。
     • lpf[25] = 5，所以nums[0]被替换为5，操作次数ans变为1。
     • 操作后数组为[5, 7]，此时5 <= 7，满足非递减。
     • 返回操作次数1。

时间复杂度和空间复杂度：

1. 时间复杂度：

   • 预处理lpf数组：使用埃拉托斯特尼筛法的变种，时间复杂度为O(mx log log mx)，其中mx = 1,000,001。这是一个近似线性的时间复杂度。
   • 处理nums数组：遍历数组一次，每次操作的时间复杂度为O(1)（因为lpf数组是预处理的），所以总时间复杂度为O(n)，其中n是数组长度。
   • 总时间复杂度：O(mx log log mx + n)。由于mx是常数（1,000,001），可以简化为O(n)。

2. 空间复杂度：

   • lpf数组的大小为mx，即O(mx)。
   • 其他变量（如ans等）占用常数空间。
   • 总空间复杂度：O(mx)，即O(1,000,001)，是常数空间。

总结：

• 预处理lpf数组是关键，它使得后续操作可以在常数时间内完成。
• 通过从右向左遍历数组，可以贪心地处理每个元素，确保每次操作都是必要的。
• 时间复杂度和空间复杂度都是线性的，但由于mx是固定的，实际表现非常高效。

Go完整代码如下：

package main

import (
	"fmt"
)

const mx = 1_000_001

var lpf = [mx]int{}

func init() {
	for i := 2; i < mx; i++ {
		if lpf[i] == 0 {
			for j := i; j < mx; j += i {
				if lpf[j] == 0 {
					lpf[j] = i
				}
			}
		}
	}
}

func minOperations(nums []int) (ans int) {
	for i := len(nums) - 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
}

func main() {
	nums := []int{25, 7}
	result := minOperations(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

mx = 1_000_001
lpf = [0] * mx

def init():
    for i in range(2, mx):
        if lpf[i] == 0:
            for j in range(i, mx, i):
                if lpf[j] == 0:
                    lpf[j] = i

def min_operations(nums):
    ans = 0
    for i in range(len(nums) - 2, -1, -1):
        if nums[i] > nums[i + 1]:
            nums[i] = lpf[nums[i]]
            if nums[i] > nums[i + 1]:
                return -1
            ans += 1
    return ans

if __name__ == '__main__':
    init()
    nums = [25, 7]
    result = min_operations(nums)
    print(result)

Rust完整代码如下：

const MX: usize = 1_000_001;

fn init_lpf() -> Vec<usize> {
    let mut lpf = vec![0; MX];
    for i in 2..MX {
        if lpf[i] == 0 {
            let mut j = i;
            while j < MX {
                if lpf[j] == 0 {
                    lpf[j] = i;
                }
                j += i;
            }
        }
    }
    lpf
}

fn min_operations(nums: &mut [usize], lpf: &[usize]) -> i32 {
    let mut ans = 0;
    for i in (0..nums.len() - 1).rev() {
        if nums[i] > nums[i + 1] {
            nums[i] = lpf[nums[i]];
            if nums[i] > nums[i + 1] {
                return -1;
            }
            ans += 1;
        }
    }
    ans
}

fn main() {
    let lpf = init_lpf();
    let mut nums = vec![25, 7];
    let result = min_operations(&mut nums, &lpf);
    println!("{}", result);
}