2026-04-21：可表示为连续质数和的最大质数。用go语言，给定一个整数 n，找出不超过 n 的最大质数，并且这个质数必须能写成“从 2 开始的

福大大架构师每日一题

发布于 2026-04-21 14:03:40

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-04-21：可表示为连续质数和的最大质数。用go语言，给定一个整数 n，找出不超过 n 的最大质数，并且这个质数必须能写成“从 2 开始的若干个连续质数的和”。如果满足条件的质数都不存在，就输出 0。

这里的“质数”指大于 1 且只有两个约数（1 和它本身）的数。

“连续质数之和”表示：例如把 2、3、5、7…按顺序取出若干个，从 2 开始连续相加，得到的结果必须等于目标质数。

1 <= n <= 500000。

输入： n = 20。

输出： 17。

解释：

小于或等于 n = 20，且是连续质数和的质数有：

2 = 2

5 = 2 + 3

17 = 2 + 3 + 5 + 7

其中最大的质数是 17，因此答案是 17。

题目来自力扣3770。

代码执行过程分步详细描述

步骤1：定义全局常量与变量（程序启动第一步）

1. 定义常量mx=500000，这是题目要求的输入最大值，所有预处理都基于这个上限；
2. 定义切片primes：用来按顺序存储所有≤500000的质数（从2开始）；
3. 定义布尔数组np：长度为500001，标记数字是否为非质数（np[x]=true表示x不是质数，false表示x是质数）；
4. 定义整数数组ans：长度为500001，ans[i]表示不超过i的、满足条件的最大质数（核心结果数组）。

步骤2：执行init函数第一部分——埃拉托斯特尼筛法生成质数表

init函数是Go的初始化函数，程序运行main前自动执行，第一部分用筛法高效生成所有≤500000的质数：

1. 从数字2开始遍历到500000；
2. 如果当前数字i没被标记为非质数（np[i]=false），说明i是质数，将它加入primes切片；
3. 把这个质数i的所有平方及以上的倍数，全部标记为非质数（np[j]=true）；
4. 遍历结束后，primes切片就按顺序存好了：2、3、5、7、11、13、17、19……所有≤500000的质数，np数组也完成了质数标记。

步骤3：执行init函数第二部分——预处理ans结果数组

这一步是核心逻辑，计算出每个数字i（2≤i≤500000）对应的答案ans[i]：

1. 初始化3个临时变量：
- • sum：存储从2开始的连续质数的累加和；
- • last：存储当前找到的、满足条件的最大质数（初始为0）；
- • j：primes切片的索引，用来依次取连续质数；
2. 从2遍历到500000，逐个计算ans[i]：
- • 判断：下一个质数（primes[j]）加到sum里，结果是否≤当前数字i；
- • 如果满足：把这个质数加到sum中，索引j向后移一位（取下一个连续质数）；
- • 检查新的sum是不是质数（np[sum]=false）：如果是，就更新last为这个sum；
- • 把当前的last赋值给ans[i]（ans[i]就是≤i的最大符合条件质数）；
3. 遍历结束后，ans数组预处理完成：比如ans[20]=17、ans[5]=5、ans[2]=2。

步骤4：调用largestPrime函数查询结果

这个函数是O(1)直接查询：传入目标数字n，直接返回预处理好的ans[n]，就是最终答案。

步骤5：main函数执行与输出

1. 定义输入n=20；
2. 调用largestPrime(20)得到结果17；
3. 打印输出结果。

关键逻辑补充（结合示例n=20）

我们用n=20验证预处理过程，清晰理解满足条件的质数：

1. 累加2 → sum=2（质数）→ last=2 → ans[2]=2；
2. 累加3 → sum=5（质数）→ last=5 → ans[5]=5；
3. 累加5 → sum=10（非质数）→ last不变；
4. 累加7 → sum=17（质数）→ last=17 → ans[17]=17；
5. 继续累加11 → sum=28（超过20，停止）；最终≤20的符合条件质数：2、5、17，最大为17。

时间复杂度分析

整体时间复杂度由筛法和ans数组预处理两部分组成：

1. 埃氏筛法时间复杂度：O(mx log log mx)，这是筛法的标准复杂度，远快于暴力遍历；
2. ans数组预处理时间复杂度：O(mx)，仅一次遍历到500000，质数累加是线性操作；
3. 总时间复杂度：O(mx log log mx)（mx=500000），属于高效的线性级复杂度。

额外空间复杂度分析

额外空间指除输入输出外，程序运行占用的内存空间：

1. primes切片：存储≤500000的质数，空间O(mx / log mx)（质数密度公式）；
2. np布尔数组：O(mx)；
3. ans整数数组：O(mx)；
4. 临时变量：常数级O(1)；
5. 总额外空间复杂度：O(mx)（mx=500000），属于线性空间复杂度。

总结

1. 执行流程：全局变量定义→筛法生成质数表→预处理答案数组→O(1)查询结果→输出；
2. 核心优化：提前预处理所有可能输入的答案，查询时直接取值，效率极高；
3. 总时间复杂度：O(mx log log mx)（mx=5e5）；
4. 总额外空间复杂度：O(mx)（mx=5e5）。

Go完整代码如下：

package main

import (
    "fmt"
)

const mx = 500_000

var primes []int
var np [mx + 1]bool
var ans [mx + 1]int

func init() {
    for i := 2; i <= mx; i++ {
        if !np[i] {
            primes = append(primes, i)
            for j := i * i; j <= mx; j += i {
                np[j] = true
            }
        }
    }

    sum, last, j := 0, 0, 0
    for i := 2; i <= mx; i++ {
        if sum+primes[j] <= i {
            sum += primes[j]
            j++
            if !np[sum] {
                last = sum
            }
        }
        ans[i] = last
    }
}

func largestPrime(n int)int {
    return ans[n]
}

func main() {
    n := 20
    result := largestPrime(n)
    fmt.Println(result)
}

Python完整代码如下：

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

def init_data(mx=500_000):
    primes = []
    np = [False] * (mx + 1)
    
    # 筛法求素数
    for i in range(2, mx + 1):
        if not np[i]:
            primes.append(i)
            for j in range(i * i, mx + 1, i):
                np[j] = True
    
    ans = [0] * (mx + 1)
    sum_val, last, j = 0, 0, 0
    
    for i in range(2, mx + 1):
        if j < len(primes) and sum_val + primes[j] <= i:
            sum_val += primes[j]
            j += 1
            if not np[sum_val]:
                last = sum_val
        ans[i] = last
    
    return ans

def largest_prime(n):
    ans = init_data()
    return ans[n]

if __name__ == "__main__":
    n = 20
    result = largest_prime(n)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>

constint mx = 500000;

std::vector<int> primes;
std::vector<bool> np(mx + 1, false);
std::vector<int> ans(mx + 1, 0);

void init() {
    // 筛法求素数
    for (int i = 2; i <= mx; i++) {
        if (!np[i]) {
            primes.push_back(i);
            if ((long long)i * i <= mx) {  // 防止整数溢出
                for (int j = i * i; j <= mx; j += i) {
                    np[j] = true;
                }
            }
        }
    }

    int sum = 0, last = 0, j = 0;
    for (int i = 2; i <= mx; i++) {
        if (j < primes.size() && sum + primes[j] <= i) {
            sum += primes[j];
            j++;
            if (!np[sum]) {
                last = sum;
            }
        }
        ans[i] = last;
    }
}

int largestPrime(int n) {
    return ans[n];
}

int main() {
    init();  // 初始化数据

    int n = 20;
    int result = largestPrime(n);
    std::cout << result << std::endl;

    return0;
}