如何优化无循环实现回文素数查找的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
相关产品推荐
相关产品推荐

