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 开始遍历，只要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.内层循环递增
对于当前位置的数值x，检查notPrime[x]是否等于i % 2：

这个循环保证了每个元素通过最少次数的“加 1”操作，达到离它最近的一个满足条件的值（向上搜索第一个符合条件的数）。

• •如果不等：说明当前值不满足条件。由于只能做“加 1”操作，于是将x增加 1，同时操作次数ans加 1，然后再次判断新x是否满足条件。

• •循环终止条件：当notPrime[x] == i % 2时停止，此时x满足该索引位置的要求（偶数索引时 x 是质数，奇数索引时 x 是非质数）。

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++完整代码如下：

  

  

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& 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 nums = {1, 2, 3, 4};
    int result = minOperations(nums);
    cout << result << endl;
    return 0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。