Medium

题目描述

给定一个整数 n。

返回小于或等于 n 的最大质数，该质数可以表示为从 2 开始的一个或多个连续质数的和。如果不存在这样的数，返回 0。

示例 1：

输入：n = 20
输出：17
解释：
小于或等于 n = 20 的质数中，可以表示为连续质数和的有：
2 = 2
5 = 2 + 3
17 = 2 + 3 + 5 + 7
最大的是 17，所以答案是 17。

示例 2：

输入：n = 2
输出：2
解释：
小于或等于 2 的唯一连续质数和是 2 本身。

约束条件：

  • 1 <= n <= 5 * 10^5

提示：

  • 生成所有小于等于 n 的质数（使用埃拉托斯特尼筛法或试除法）
  • 计算从 2 开始的连续和，直到和超过 n
  • 找到既是质数又是连续质数和的最大值

解题思路

解题思路

这是一道综合性的数论题，需要结合质数生成和前缀和计算。

核心思路：

  1. 生成质数：使用埃拉托斯特尼筛法生成所有小于等于 n 的质数
  2. 计算连续和：从质数 2 开始，计算所有可能的连续质数和
  3. 记录有效和：将所有小于等于 n 且为质数的连续和记录下来
  4. 返回最大值：从所有有效的连续质数和中返回最大值

具体步骤：

  • 使用筛法生成质数列表和质数判断数组
  • 对于每个起始位置，累加连续质数直到和超过 n
  • 在累加过程中，如果当前和是质数且小于等于 n，则更新答案
  • 由于我们要找最大值，从大到小遍历或者维护最大值即可

优化点：

  • 使用埃拉托斯特尼筛法预处理，时间复杂度 O(n log log n)
  • 连续和的计算是 O(质数个数²)，实际上质数密度不高，效率可接受
  • 可以用前缀和优化，但由于要枚举所有起始位置，时间复杂度本质相同

代码实现

class Solution {
public:
    int largestPrime(int n) {
        // 埃拉托斯特尼筛法生成质数
        vector<bool> isPrime(n + 1, true);
        vector<int> primes;
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.push_back(i);
                for (long long j = (long long)i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int result = 0;
        
        // 枚举所有可能的连续质数和
        for (int i = 0; i < primes.size(); i++) {
            int sum = 0;
            for (int j = i; j < primes.size(); j++) {
                sum += primes[j];
                if (sum > n) break;
                if (isPrime[sum]) {
                    result = max(result, sum);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def largestPrime(self, n: int) -> int:
        # 埃拉托斯特尼筛法生成质数
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        primes = []
        
        for i in range(2, n + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
        
        result = 0
        
        # 枚举所有可能的连续质数和
        for i in range(len(primes)):
            sum_val = 0
            for j in range(i, len(primes)):
                sum_val += primes[j]
                if sum_val > n:
                    break
                if is_prime[sum_val]:
                    result = max(result, sum_val)
        
        return result

public class Solution {
    public int LargestPrime(int n) {
        // 埃拉托斯特尼筛法生成质数
        bool[] isPrime = new bool[n + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        List<int> primes = new List<int>();
        
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.Add(i);
                for (long j = (long)i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int result = 0;
        
        // 枚举所有可能的连续质数和
        for (int i = 0; i < primes.Count; i++) {
            int sum = 0;
            for (int j = i; j < primes.Count; j++) {
                sum += primes[j];
                if (sum > n) break;
                if (isPrime[sum]) {
                    result = Math.Max(result, sum);
                }
            }
        }
        
        return result;
    }
}

var largestPrime = function(n) {
    // 埃拉托斯特尼筛法生成质数
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    const primes = [];
    
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let result = 0;
    
    // 枚举所有可能的连续质数和
    for (let i = 0; i < primes.length; i++) {
        let sum = 0;
        for (let j = i; j < primes.length; j++) {
            sum += primes[j];
            if (sum > n) break;
            if (isPrime[sum]) {
                result = Math.max(result, sum);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log log n + p²)，其中 p 是小于等于 n 的质数个数。筛法需要 O(n log log n)，枚举连续和需要 O(p²)
空间复杂度O(n + p)，需要 O(n) 空间存储筛法数组，O(p) 空间存储质数列表