You need to enable JavaScript to run this app. 如何优化无循环实现回文素数查找的Python递归函数代码
优惠活动
大模型
产品
解决方案
定价
更多

如何优化无循环实现回文素数查找的Python递归函数代码

现有代码问题检查

你的原有代码功能逻辑正确,可以输出符合要求的结果,但存在以下可优化的问题:

  • 素数判断效率极低:递归判断素数时从1遍历到数字本身,数字较大时递归深度极高、运算速度极慢
  • 回文数判断冗余:需要生成完整的反转字符串再做比较,产生不必要的递归操作和内存占用
  • 输入存在安全风险:使用eval()接收用户输入,若用户输入恶意代码会被直接执行
  • 存在不必要的排序步骤:从M倒序遍历到N收集结果,最后需要额外排序,多出不必要的操作步骤
  • 没有利用回文素数的特性做剪枝,大量无效计算没有被提前过滤
优化思路
  • 素数判断逻辑优化:终止条件改为除数大于等于数字的平方根,因为如果一个数n有大于√n的因子,对应的另一个因子必然小于√n,无需遍历到n本身即可完成判断
  • 回文数判断逻辑优化:递归直接比较字符串首尾字符,不需要生成完整反转串,匹配失败直接返回,大幅减少计算量
  • 新增剪枝规则:除了11之外,所有偶数位数的回文数都能被11整除,不可能是素数,直接跳过这类数的判断,大幅降低运算量
  • 输入安全优化:用int()替换eval(),避免代码注入风险
  • 遍历逻辑优化:改为从小到大从N遍历到M,收集结果无需额外排序
  • 代码规范优化:避免使用全局变量存储结果,改为函数返回值传递,逻辑更清晰
优化后带注释代码
import sys
import math
# 调整递归深度上限,避免数字较大时递归深度不足报错
sys.setrecursionlimit(30000)

# 递归判断是否为素数
def is_prime(n, divisor=2):
    # 终止条件1:除数大于等于n的平方根,说明没有找到因子,是素数
    if divisor > math.isqrt(n):
        return True
    # 终止条件2:能被除数整除,不是素数
    if n % divisor == 0:
        return False
    # 递归调用,除数加1继续判断
    return is_prime(n, divisor + 1)

# 递归判断是否为回文数
def is_palindrome(s):
    # 终止条件1:字符串长度小于等于1,说明所有首尾字符都匹配,是回文数
    if len(s) <= 1:
        return True
    # 终止条件2:首尾字符不匹配,不是回文数
    if s[0] != s[-1]:
        return False
    # 递归调用,去掉首尾字符继续判断
    return is_palindrome(s[1:-1])

# 递归遍历[N, M]区间,收集所有回文素数
def get_palindrome_primes(current, end):
    # 终止条件:当前数超过上限,返回空列表
    if current > end:
        return []
    # 剪枝:除了11之外,偶数位长度的数不可能是回文素数,直接跳过
    s = str(current)
    if current != 11 and len(s) % 2 == 0:
        return get_palindrome_primes(current + 1, end)
    # 判断当前数是否是回文素数
    if is_palindrome(s) and is_prime(current):
        # 符合条件,加入结果列表,继续递归下一个数
        return [current] + get_palindrome_primes(current + 1, end)
    # 不符合条件,直接递归下一个数
    return get_palindrome_primes(current + 1, end)

# 递归打印结果列表
def print_result(lst, pos=0):
    # 终止条件:打印完所有元素
    if pos >= len(lst):
        return
    print(lst[pos])
    # 递归打印下一个元素
    print_result(lst, pos + 1)

# 主逻辑
if __name__ == "__main__":
    # 读取输入,用int替代eval保证安全
    N = int(input("Enter the starting point N: \n"))
    M = int(input("Enter the ending point M: \n"))
    print("The palindromic primes are:")
    # 获取回文素数列表
    res = get_palindrome_primes(N, M)
    # 打印结果
    print_result(res)
测试验证

使用你提供的示例输入:输入N=200,M=800,输出结果和示例完全一致:

313
353
373
383
727
757
787
797

内容的提问来源于stack exchange,提问作者user16053605

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.17 02:36:02