网硕互联帮助中心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。
初始化标记数组
- notPrime[0] 和 notPrime[1] 被标记为 1，因为 0 和 1 不是质数。
- 其余位置初始为 0，表示暂时认为是质数。
埃拉托色尼筛法
- 从 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，对每个元素根据其索引的奇偶性进行不同处理，并累加操作次数。
遍历数组
用 for i, x := range nums 同时获取索引 i 和对应的值 x。
确定目标条件
- 如果 i 是偶数（i % 2 == 0），要求该位置的最终值必须是质数，即 notPrime[x] 最终应该等于 0。
- 如果 i 是奇数（i % 2 == 1），要求该位置的最终值必须是非质数，即 notPrime[x] 最终应该等于 1。
用 i % 2 正好可以表达这个期望值：
- 偶数索引期望 notPrime[x] == 0
- 奇数索引期望 notPrime[x] == 1
内层循环递增
对于当前位置的数值 x，检查 notPrime[x] 是否等于 i % 2：
- 如果不等：说明当前值不满足条件。由于只能做“加 1”操作，于是将 x 增加 1，同时操作次数 ans 加 1，然后再次判断新 x 是否满足条件。
- 循环终止条件：当 notPrime[x] == i % 2 时停止，此时 x 满足该索引位置的要求（偶数索引时 x 是质数，奇数索引时 x 是非质数）。
这个循环保证了每个元素通过最少次数的“加 1”操作，达到离它最近的一个满足条件的值（向上搜索第一个符合条件的数）。
累加结果
每处理完一个元素，其所需的操作次数已经累加到 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。
四、时间复杂度分析
质数预计算
埃氏筛的时间复杂度为 O(M log log M)，其中 M = 100004。这是一个常数上限，所以是 O(1)。
主循环
对数组中每个元素，内层的 for 循环会让 x 递增，直到找到符合条件的值。在最坏情况下，每次可能跨越多个数，但每个数最多递增到下一个符合条件的值，而质数和非质数的间隔是有限的。由于质数分布相对密集（在 1e5 范围内最大间隔不超过几百），实际上内层循环执行次数与数组长度 n 成线性关系，总体可以认为是 O(n)。
如果严格分析，每个位置的操作次数等于“到达下一个符合条件的数的距离”，所有距离之和不会超过某个常数乘以 n（因为数值范围有限，质数间隙有界），因此仍是 O(n)。
总时间复杂度：O(n)，其中 n 是数组长度。
五、空间复杂度分析
notPrime 数组
大小为 100004 的整型数组，占用常数级额外空间，O(1)。
其他变量
只用了几个整型变量（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;
}
评论前必须登录！
注册