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. 初始化标记数组

   • 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. 遍历数组
   用for i, x := range nums同时获取索引i和对应的值x。

2. 确定目标条件

   • 如果i是偶数（i % 2 == 0），要求该位置的最终值必须是质数，即notPrime[x]最终应该等于0。
   • 如果i是奇数（i % 2 == 1），要求该位置的最终值必须是非质数，即notPrime[x]最终应该等于1。

   用i % 2正好可以表达这个期望值：

   • 偶数索引期望notPrime[x] == 0
   • 奇数索引期望notPrime[x] == 1

3. 内层循环递增
   对于当前位置的数值x，检查notPrime[x]是否等于i % 2：

   • 如果不等：说明当前值不满足条件。由于只能做“加 1”操作，于是将x增加 1，同时操作次数ans加 1，然后再次判断新x是否满足条件。
   • 循环终止条件：当notPrime[x] == i % 2时停止，此时x满足该索引位置的要求（偶数索引时 x 是质数，奇数索引时 x 是非质数）。

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

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. 质数预计算
   埃氏筛的时间复杂度为 O(M log log M)，其中 M = 100004。这是一个常数上限，所以是 O(1)。

2. 主循环
   对数组中每个元素，内层的for循环会让x递增，直到找到符合条件的值。在最坏情况下，每次可能跨越多个数，但每个数最多递增到下一个符合条件的值，而质数和非质数的间隔是有限的。由于质数分布相对密集（在 1e5 范围内最大间隔不超过几百），实际上内层循环执行次数与数组长度 n 成线性关系，总体可以认为是 O(n)。

   如果严格分析，每个位置的操作次数等于“到达下一个符合条件的数的距离”，所有距离之和不会超过某个常数乘以 n（因为数值范围有限，质数间隙有界），因此仍是 O(n)。

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

五、空间复杂度分析

1. notPrime 数组
   大小为 100004 的整型数组，占用常数级额外空间，O(1)。

2. 其他变量
   只用了几个整型变量（i, x, ans 等），O(1)。

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

Go完整代码如下：

packagemainimport("fmt")constmx=100_004// 1e5 的下一个质数是 1e5 + 3varnotPrime=[mx]int{1,1}funcinit(){fori:=2;i*i<mx;i++{ifnotPrime[i]==0{forj:=i*i;j<mx;j+=i{notPrime[j]=1}}}}funcminOperations(nums[]int)(ansint){fori,x:=rangenums{// 如果 i 是偶数，那么循环直到 notPrime[x] == 0（x 是质数）// 如果 i 是奇数，那么循环直到 notPrime[x] == 1（x 不是质数）fornotPrime[x]!=i%2{ans++x++}}return}funcmain(){nums:=[]int{1,2,3,4}result:=minOperations(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defmin_operations(nums):mx=100004# 1e5 的下一个质数是 1e5 + 3not_prime=[0]*mx not_prime[0]=not_prime[1]=1# 埃氏筛标记非质数foriinrange(2,int(mx**0.5)+1):ifnot_prime[i]==0:forjinrange(i*i,mx,i):not_prime[j]=1ans=0fori,xinenumerate(nums):# 如果 i 是偶数，需要 not_prime[x] == 0（x 是质数）# 如果 i 是奇数，需要 not_prime[x] == 1（x 不是质数）whilenot_prime[x]!=i%2:ans+=1x+=1returnansif__name__=="__main__":nums=[1,2,3,4]result=min_operations(nums)print(result)

C++完整代码如下：

#include<iostream>#include<vector>usingnamespacestd;constintmx=100004;// 1e5 的下一个质数是 1e5 + 3intnotPrime[mx]={1,1};// 初始化埃氏筛voidinit(){for(inti=2;i*i<mx;i++){if(notPrime[i]==0){for(intj=i*i;j<mx;j+=i){notPrime[j]=1;}}}}intminOperations(vector<int>&nums){intans=0;for(inti=0;i<nums.size();i++){intx=nums[i];// 如果 i 是偶数，需要 notPrime[x] == 0（x 是质数）// 如果 i 是奇数，需要 notPrime[x] == 1（x 不是质数）while(notPrime[x]!=i%2){ans++;x++;}}returnans;}intmain(){init();// 初始化质数表vector<int>nums={1,2,3,4};intresult=minOperations(nums);cout<<result<<endl;return0;}