Superprime：每个十进制前缀都是质数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 长度L是给定正整数，不允许前导0；每个非空十进制前缀都要质数。
• 不是每个后缀也质数，亦不是质数在质数列表里的序号为质数。

解题路线

1. 一位候选为2/3/5/7。扩展为10p+d，新数若质数则保留；旧所有前缀已验证，所以只需检查新完整数。
2. 多位质数个位只可能1/3/7/9，因此只试这4个，不改变完备性。用trial division到√n是清晰基线，超大整数需概率/确定性质数测试合同。
3. 层层剪枝比扫描全部10^L数更省，但不能声称O(L)，候选数量和质数检查值域仍影响成本。

手动走一遍

37的前缀3和37都质数，因此是长度2 superprime；23同样满足。29满足，21因自身合数被剪；非质数前缀不会继续扩展。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def superprimes(length):
    if type(length) is not int or length<1:raise ValueError("positive decimal length required")
    def prime(n):
        if n<2:return False
        divisor=2
        while divisor*divisor<=n:
            if n%divisor==0:return False
            divisor+=1
        return True
    frontier=[2,3,5,7]
    for _ in range(1,length):
        frontier=[10*x+digit for x in frontier for digit in (1,3,7,9) if prime(10*x+digit)]
    return frontier

复杂度

设每层候选数A_l，trial primality总成本约Σ4A_(l−1)√(10^l)整数除法，上界指数；保存最大frontier。实际候选稀疏但需据测试给规模限制。

易错点与追问

容易失分的边界

• 对1误判质数会引入大量错误候选。
• 只检查最终数质数不够，必须所有前缀都合法。

继续深挖

• 要所有长度≤L结果，如何复用已有层？
• L非常大时为什么要讨论大整数测试误差与输出规模？