2025-11-07：最大质数子字符串之和。用go语言，给出一个字符串 s，从它的所有连续子串中挑出能表示质数的那些不同整数，求这类不同质数中的三个最大值之和。若不同质数不足三个，则把所有这些不同质数相加并返回结果。

说明要点：

• 子串指原字符串中连续的一段字符。

• 把子串转换为整数时，忽略前导零（例如 “007” 视为 7）。

• 质数定义为大于1且只有 1 和自身 两个正因数的整数。

• 相同的质数即使由多个不同子串得到，也只计算一次。

1 <= s.length <= 10。

s 仅由数字组成。

输入： s = “12234”。

输出： 1469。

解释：

由 “12234” 的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。

最大的 3 个质数是 1223、223 和 23。它们的和是 1469。

题目来自力扣3556。

🔍 步骤一：预处理质数表

程序首先使用埃拉托斯特尼筛法预生成一个质数表。这个预处理过程会标记出从 2 到上限 mx（值为 100,000）的所有非质数，并将所有质数保存在一个列表 primeNumbers 中。这样，当需要判断一个不超过 mx 的数是否为质数时，就可以通过查询这个布尔数组在常数时间内完成，效率非常高。

🔢 步骤二：判断大质数

对于超过预处理上限 mx 的大数，程序使用一个优化的试除法进行质数判断。具体来说，它用预先求得的质数列表 primeNumbers 中的质数作为除数，依次去试除待检测的数 n。试除过程有一个重要的优化：只需要试除到某个质数的平方大于 n 即可，因为如果 n 有大于其平方根的因子，那么它必然还有一个小于其平方根的因子。这个方法将判断质数的时间复杂度从 O(n) 优化到了 O(√n)。

🧩 步骤三：枚举所有数字子串

程序需要从输入字符串中提取出所有连续的子串，并将其转换为整数。为了避免重复计算和判断，程序采用了两层循环来枚举所有可能的子串：

• 外层循环：遍历字符串的每个起始位置 i。
• 内层循环：从起始位置 i 开始，逐步扩展子串的结束位置，并实时计算当前子串对应的整数值。这个计算过程是高效的，它在上一个子串数值的基础上乘以10，然后加上新字符对应的数字。

在转换过程中，程序自动处理了前导零。例如，子串 “007” 会被转换为整数 7。这是通过直接进行十进制整数转换实现的，前导零在计算过程中自然被忽略。

🔍 步骤四：质数筛选与收集

对于每一个通过扩展得到的整数，程序调用 isPrime 函数判断其是否为质数。如果是质数，则将其添加到一个质数列表 primes 中。这个列表在后续步骤之前可能会包含重复的质数（即使这些质数由原始字符串中不同的子串得到）。

🧹 步骤五：质数列表去重排序

为了满足题目中"不同质数"的要求，程序需要对收集到的质数列表进行去重：

1. 排序：首先使用 slices.Sort 对质数列表进行排序，为去重做准备。
2. 去重：然后使用 slices.Compact 函数移除列表中相邻的重复元素。由于排序后相同的质数会相邻排列，这个操作可以有效地得到唯一化的质数列表。

➕ 步骤六：计算最大三个质数的和

去重排序后，列表中的质数已经是从小到大排列。题目要求取最大的三个质数求和。程序通过切片操作 primes[max(len(primes)-3, 0):] 来达成目标：

• 如果不同质数的数量大于等于3个，则取最后三个（即最大的三个）。
• 如果不足三个，则 max(len(primes)-3, 0) 会确保从第0个元素开始取，也就是取全部质数。
  最后，程序将这些选中的质数相加，返回它们的和。

⏱️ 时间复杂度分析

设字符串长度为 n。

• 子串枚举：程序需要枚举 O(n²) 个子串（确切地是 n(n+1)/2 个）。对于每个子串，内层循环需要逐步构建整数，这部分操作本身是 O(n) 的。但关键在于，对于每个枚举出的整数 x，我们需要判断其是否为质数。
• 质数判断：判断质数的时间复杂度取决于 isPrime 函数。对于大于预处理上限 mx 的数，最坏情况下需要 O(√x / log √x) 的时间（用预先生成的小质数去试除）。由于字符串长度 n 最大为10，能产生的最大数字是10位数，这个判断开销是可控的，但仍然是整个算法的主要时间开销点。
  综合来看，总的时间复杂度可以表述为 O(n³ * F(n))，其中 F(n) 是判断一个由 n 位数字构成的整数是否为质数的时间开销。由于 n 很小（最大为10），这个算法是可行的。

💾 空间复杂度分析

• 预处理存储：程序预分配了大小为 mx+1（100,001）的布尔数组 np 和一个存储质数的列表 primeNumbers，这是固定的空间开销 O(mx)。
• 质数列表：在最坏情况下，可能存储 O(n²) 个质数（虽然去重后通常会少很多）。
• 递归栈/其他：其他变量占用的空间是常数级别或 O(n)。
  因此，总的额外空间复杂度主要是 O(mx + n²)。由于 mx 是固定的100,000，相对于很小的 n（最大10）来说，占主导地位的是预处理的空间开销。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

const mx = 100_000

var np = [mx + 1]bool{true, true}
var primeNumbers []int

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

func isPrime(n int) bool {
	if n <= mx {
		return !np[n]
	}
	for _, p := range primeNumbers {
		if p*p > n {
			break
		}
		if n%p == 0 {
			return false
		}
	}
	return true
}

func sumOfLargestPrimes(s string) (ans int64) {
	primes := []int{}
	n := len(s)
	for i := range n {
		x := 0
		for _, b := range s[i:] {
			x = x*10 + int(b-'0')
			if isPrime(x) {
				primes = append(primes, x)
			}
		}
	}

	slices.Sort(primes)
	primes = slices.Compact(primes) // 去重

	for _, p := range primes[max(len(primes)-3, 0):] {
		ans += int64(p)
	}
	return
}

func main() {
	s := "12234"
	result := sumOfLargestPrimes(s)
	fmt.Println(result)
}

Python完整代码如下：

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

import math

mx = 100_000
np = [True, True] + [False] * (mx - 1)  # 和 Go 中的默认值一致，np[i] = True 表示非质数
primeNumbers = []

# 初始化质数表（埃氏筛）
for i in range(2, mx + 1):
    if not np[i]:
        primeNumbers.append(i)
        for j in range(i * i, mx + 1, i):
            np[j] = True

def is_prime(n: int) -> bool:
    """判断一个数是否是质数"""
    if n <= mx:
        return not np[n]
    for p in primeNumbers:
        if p * p > n:
            break
        if n % p == 0:
            return False
    return True

def sum_of_largest_primes(s: str) -> int:
    primes = []
    n = len(s)
    # 遍历所有可能的子串
    for i in range(n):
        x = 0
        for b in s[i:]:
            x = x * 10 + (ord(b) - ord('0'))
            if is_prime(x):
                primes.append(x)
    
    # 去重并排序
    primes = sorted(set(primes))
    # 取最大的三个质数求和
    return sum(primes[-3:]) if len(primes) >= 3 else sum(primes)

if __name__ == "__main__":
    s = "12234"
    result = sum_of_largest_primes(s)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_set>
#include <windows.h> 
using namespace std;

const int MX = 100000;

// 全局变量：素数标记数组和素数列表
vector<bool> np(MX + 1, false);
vector<int> primeNumbers;

// 初始化函数：使用埃拉托斯特尼筛法预计算素数
void initPrimes() {
    // 初始化：0和1不是素数
    np[0] = np[1] = true;
    
    for (int i = 2; i <= MX; i++) {
        if (!np[i]) {
            primeNumbers.push_back(i);
            // 标记i的所有倍数为非素数
            for (long long j = (long long)i * i; j <= MX; j += i) {
                np[j] = true;
            }
        }
    }
}

// 判断一个数是否为素数
bool isPrime(int n) {
    if (n <= 1) return false;
    
    // 如果在预计算范围内，直接返回结果
    if (n <= MX) {
        return !np[n];
    }
    
    // 对于大数，使用试除法（用已知的小素数进行测试）
    for (int p : primeNumbers) {
        if ((long long)p * p > n) {
            break;
        }
        if (n % p == 0) {
            return false;
        }
    }
    return true;
}

// 从字符串中提取素数并返回最大的三个素数之和
long long sumOfLargestPrimes(const string& s) {
    unordered_set<int> primesSet;  // 使用集合来自动去重
    int n = s.length();
    
    // 生成所有可能的数字子串
    for (int i = 0; i < n; i++) {
        int x = 0;
        // 从位置i开始生成所有可能的数字
        for (int j = i; j < n; j++) {
            x = x * 10 + (s[j] - '0');
            if (isPrime(x)) {
                primesSet.insert(x);
            }
        }
    }
    
    // 如果没有找到素数，返回0
    if (primesSet.empty()) {
        return 0;
    }
    
    // 将集合转换为向量并排序
    vector<int> primes(primesSet.begin(), primesSet.end());
    sort(primes.begin(), primes.end());
    
    // 取最大的三个素数（如果不足三个则取全部）
    int startIdx = primes.size() >= 3 ? primes.size() - 3 : 0;
    long long sum = 0;
    for (int i = startIdx; i < primes.size(); i++) {
        sum += primes[i];
    }
    
    return sum;
}

int main() {
    SetConsoleOutputCP(CP_UTF8); // CP_UTF8 就是 65001
    // 初始化素数表
    initPrimes();
    
    string s = "12234";
    long long result = sumOfLargestPrimes(s);
    cout << "字符串 \"" << s << "\" 中最大的三个素数之和为: " << result << endl;
    
    return 0;
}