数字串中最长质数子串的算法实现与优化

1. 问题背景与需求分析

最近在辅导孩子学习质数概念时，遇到了一个有趣的编程问题。题目要求从一个数字串中找出最长的质数子串，且这个子串的长度不超过4个字符。如果有多个相同长度的质数子串，则选择数值最大的那个。

这个问题看似简单，但实际上涉及了几个关键点：

• 质数判断：如何高效判断一个数是否为质数
• 子串提取：如何从数字串中提取所有可能的子串
• 结果筛选：如何从所有可能的质数子串中找出符合要求的结果

在实际编程中，我发现这个问题非常适合用来练习字符串处理和基础算法。通过解决这个问题，不仅可以巩固质数判断的知识，还能提升对字符串操作的理解。

2. 解决方案设计思路

2.1 整体算法流程

我设计的解决方案主要分为以下几个步骤：

1. 遍历数字串，提取所有长度不超过4的子串
2. 将子串转换为整数并判断是否为质数
3. 记录满足条件的质数，优先保留长度更长的子串
4. 对于相同长度的子串，保留数值更大的那个

这个流程看似简单，但在实现时需要考虑很多细节问题，比如：

• 如何高效生成所有可能的子串
• 如何处理边界条件（如空串、全非质数串等）
• 如何优化质数判断的效率

2.2 质数判断优化

质数判断是这个问题中最耗时的部分。我采用了以下优化策略：

• 首先排除小于2的数（非质数）
• 只需检查2到√n之间的整数是否能整除n
• 提前处理一些特殊情况（如偶数）

这种优化虽然简单，但对于n≤10000的情况已经足够高效。在实际测试中，这种判断方法可以在O(√n)时间内完成质数检测。

3. 代码实现详解

3.1 质数判断函数

cpp复制bool is_prime(int n) {
    if(n < 2) return false;  // 小于2的数不是质数
    for(int i = 2; i * i <= n; ++i) {
        if(n % i == 0)
            return false;
    }
    return true;
}

这个函数实现了基本的质数判断逻辑。关键点在于循环条件i*i <= n，这相当于只检查到√n，可以显著减少循环次数。

3.2 主处理函数

cpp复制string max_prime_substr(