2026-07-26：将数组转换为交替质数数组的最少操作次数。用go语言，给定一个整数数组 `nums`，你需要通过最少的操作次数，把它变成满足特

2026-07-26：将数组转换为交替质数数组的最少操作次数。用go语言，给定一个整数数组 nums，你需要通过最少的操作次数，把它变成满足特定规律的数组。

规律是：

• • 数组中所有索引为偶数的位置，最终的值必须是质数。
• • 所有索引为奇数的位置，最终的值必须是非质数。

每次操作只能让任意位置的元素加 1。

目标是求出让整个数组满足这个条件所需的最少操作次数。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

输入： nums = [1,2,3,4]。

输出： 3。

解释：

下标 0 处的元素必须是质数。将 nums[0] = 1 增加到 2，使用 1 次操作。

下标 1 处的元素必须是非质数。将 nums[1] = 2 增加到 4，使用 2 次操作。

下标 2 处的元素已经是质数。

下标 3 处的元素已经是非质数。

总操作次数 = 1 + 2 = 3。

题目来自力扣3896。

大体步骤如下：

一、质数预计算阶段

在 init() 函数中，代码预先构建了一个质数标记数组 notPrime，长度为 100_004。

1. 1. 初始化标记数组
   • • notPrime[0] 和 notPrime[1] 被标记为 1，因为 0 和 1 不是质数。
   • • 其余位置初始为 0，表示暂时认为是质数。
2. 2. 埃拉托色尼筛法
   • • 从 2 开始遍历，只要 i * i < mx（即 i <= 316 左右），检查 notPrime[i]。
   • • 如果 notPrime[i] == 0（说明 i 是质数），则将 i 的所有倍数（从 i * i 开始）标记为 1（非质数）。
   • • 筛选完成后，notPrime[p] == 0 表示 p 是质数，notPrime[p] == 1 表示 p 不是质数。

这里的数组大小取 100_004 是因为题目中元素最大值是 100000，而操作是不断增加数值，可能超出原最大值。选用大于 1e5 的下一个质数 100003 再加 1，确保在增加过程中查询质数属性时不越界。

二、主处理过程 minOperations

函数遍历输入数组 nums，对每个元素根据其索引的奇偶性进行不同处理，并累加操作次数。

1. 1. 遍历数组 用 for i, x := range nums 同时获取索引 i 和对应的值 x。
2. 2. 确定目标条件用 i % 2 正好可以表达这个期望值：
   • • 偶数索引期望 notPrime[x] == 0
   • • 奇数索引期望 notPrime[x] == 1
   • • 如果 i 是偶数（i % 2 == 0），要求该位置的最终值必须是质数，即 notPrime[x] 最终应该等于 0。
   • • 如果 i 是奇数（i % 2 == 1），要求该位置的最终值必须是非质数，即 notPrime[x] 最终应该等于 1。
3. 3. 内层循环递增 对于当前位置的数值 x，检查 notPrime[x] 是否等于 i % 2：这个循环保证了每个元素通过最少次数的“加 1”操作，达到离它最近的一个满足条件的值（向上搜索第一个符合条件的数）。
   • • 如果不等：说明当前值不满足条件。由于只能做“加 1”操作，于是将 x 增加 1，同时操作次数 ans 加 1，然后再次判断新 x 是否满足条件。
   • • 循环终止条件：当 notPrime[x] == i % 2 时停止，此时 x 满足该索引位置的要求（偶数索引时 x 是质数，奇数索引时 x 是非质数）。
4. 4. 累加结果 每处理完一个元素，其所需的操作次数已经累加到 ans 中。遍历结束后，ans 就是整个数组变为交替质数/非质数数组的最少总操作次数。

三、示例执行过程

以 nums = [1, 2, 3, 4] 为例：

• • i=0（偶数，期望质数）：x=1，notPrime[1] == 1 ≠ 0，递增到 2（质数），操作 +1。
• • i=1（奇数，期望非质数）：x=2，notPrime[2] == 0 ≠ 1，递增到 3（质数，操作 +1，仍不满足），递增到 4（非质数，操作 +1），共 +2。
• • i=2（偶数，期望质数）：x=3，notPrime[3] == 0 == 0，已满足，操作 +0。
• • i=3（奇数，期望非质数）：x=4，notPrime[4] == 1 == 1，已满足，操作 +0。

总操作次数 = 1 + 2 + 0 + 0 = 3。

四、时间复杂度分析

1. 1. 质数预计算 埃氏筛的时间复杂度为 O(M log log M)，其中 M = 100004。这是一个常数上限，所以是 O(1)。
2. 2. 主循环 对数组中每个元素，内层的 for 循环会让 x 递增，直到找到符合条件的值。在最坏情况下，每次可能跨越多个数，但每个数最多递增到下一个符合条件的值，而质数和非质数的间隔是有限的。由于质数分布相对密集（在 1e5 范围内最大间隔不超过几百），实际上内层循环执行次数与数组长度 n 成线性关系，总体可以认为是 O(n)。如果严格分析，每个位置的操作次数等于“到达下一个符合条件的数的距离”，所有距离之和不会超过某个常数乘以 n（因为数值范围有限，质数间隙有界），因此仍是 O(n)。

总时间复杂度：O(n)，其中 n 是数组长度。

五、空间复杂度分析

1. 1. notPrime 数组 大小为 100004 的整型数组，占用常数级额外空间，O(1)。
2. 2. 其他变量 只用了几个整型变量（i, x, ans 等），O(1)。

总额外空间复杂度：O(1)。

Go完整代码如下：

.

package main

import (
    "fmt"
)

const mx = 100_004 // 1e5 的下一个质数是 1e5 + 3
var notPrime = [mx]int{1, 1}

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

func minOperations(nums []int) (ans int) {
    for i, x := range nums {
        // 如果 i 是偶数，那么循环直到 notPrime[x] == 0（x 是质数）
        // 如果 i 是奇数，那么循环直到 notPrime[x] == 1（x 不是质数）
        for notPrime[x] != i%2 {
            ans++
            x++
        }
    }
    return
}

func main() {
    nums := []int{1, 2, 3, 4}
    result := minOperations(nums)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

.

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

def min_operations(nums):
    mx = 100004  # 1e5 的下一个质数是 1e5 + 3
    not_prime = [0] * mx
    not_prime[0] = not_prime[1] = 1

    # 埃氏筛标记非质数
    for i in range(2, int(mx ** 0.5) + 1):
        if not_prime[i] == 0:
            for j in range(i * i, mx, i):
                not_prime[j] = 1

    ans = 0
    for i, x in enumerate(nums):
        # 如果 i 是偶数，需要 not_prime[x] == 0（x 是质数）
        # 如果 i 是奇数，需要 not_prime[x] == 1（x 不是质数）
        while not_prime[x] != i % 2:
            ans += 1
            x += 1

    return ans


if __name__ == "__main__":
    nums = [1, 2, 3, 4]
    result = min_operations(nums)
    print(result)

在这里插入图片描述

C++完整代码如下：

.

#include <iostream>
#include <vector>
using namespace std;

const int mx = 100004; // 1e5 的下一个质数是 1e5 + 3
int notPrime[mx] = {1, 1};

// 初始化埃氏筛
void init() {
    for (int i = 2; i * i < mx; i++) {
        if (notPrime[i] == 0) {
            for (int j = i * i; j < mx; j += i) {
                notPrime[j] = 1;
            }
        }
    }
}

int minOperations(vector<int>& nums) {
    int ans = 0;
    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        // 如果 i 是偶数，需要 notPrime[x] == 0（x 是质数）
        // 如果 i 是奇数，需要 notPrime[x] == 1（x 不是质数）
        while (notPrime[x] != i % 2) {
            ans++;
            x++;
        }
    }
    return ans;
}

int main() {
    init(); // 初始化质数表
    vector<int> nums = {1, 2, 3, 4};
    int result = minOperations(nums);
    cout << result << endl;
    return 0;
}

在这里插入图片描述