Python实现回文素数查找的算法优化与LeetCode超时解决
超时问题核心定位
两个直接导致超时的硬伤
- 循环内的偶数位跳过逻辑完全失效
Python的for i in range(...)在启动时就会预生成整个迭代序列,循环体内对i的修改完全不会影响下一轮迭代拿到的数值。你写的if len(str(i))%2 ==0: i +=2本质上是无效操作,根本达不到跳过偶数长度数字的目的。 - 遍历了完全不存在回文素数的无效区间
数论有固定结论:所有偶数长度的回文数,除了11本身,都能被11整除,不可能是素数。对应到数值范围,从10000000(8位)到99999999(8位)的整段区间,不存在任何回文素数。
你测试的输入9989900是7位数,程序本来应该在7位区间查找完后,直接跳过整整9000万范围的8位无效区间,但因为跳过逻辑失效,程序会在这9000万区间里逐一遍历所有奇数,这部分就占了9秒运行时间的90%以上。
无依赖优化方案
- 放弃逐数扫描判断回文的思路,改成按回文规则直接生成候选:长度为L的回文,只需要取前半段的数字,镜像拼接出完整回文即可。比如生成5位回文,只需要遍历100到999的前半段数值,总共900次生成操作,比遍历90万个数字判断回文快上千倍。
- 遇到偶数长度的数值区间,直接整体跳过,不做任何遍历:比如当前候选数长度是8位,直接把起点跳到8位上限之后的9位区间,完全避免无效循环。
- 提前筛掉不可能的素数候选:如果生成的回文最后一位是0、2、4、6、8或者5,直接跳过素数判断,这类数除了2和5本身都不可能是素数,能省掉大半校验时间。
优化后参考实现
def is_prime(num: int) -> bool: if num < 2: return False if num in (2, 3, 5): return True if num % 6 not in (1, 5): return False for i in range(5, int(num**0.5) + 1, 6): if num % i == 0 or num % (i + 2) == 0: return False return True def generate_palindrome(length: int, half_val: int) -> int: s = str(half_val) if length % 2 == 0: return int(s + s[::-1]) return int(s + s[-2::-1]) class Solution: def primePalindrome(self, N: int) -> int: # 提前处理边缘小数值 if N <= 2: return 2 if N <= 3: return 3 if N <= 4: return 5 if N <= 7: return 7 if N <= 11: return 11 current_len = len(str(N)) while True: # 偶数长度直接跳过,无除11外的回文素数 if current_len % 2 == 0: current_len += 1 continue # 计算当前长度下回文前半段的遍历范围 half_start = 10 ** ((current_len - 1) // 2) half_end = 10 ** ((current_len + 1) // 2) for half in range(half_start, half_end): pal = generate_palindrome(current_len, half) if pal < N: continue # 末位为偶数或5的数不可能是除2、5外的素数 if pal % 10 in (0, 2, 4, 5, 6, 8): continue if is_prime(pal): return pal current_len += 1
用这套实现跑9989900的测试用例,运行时间会从原来的9秒降到毫秒级——因为整个8位无效区间被直接跳过,从7位查找结束后直接生成9位的回文候选,全程只需要生成不到1000个候选数,不存在任何无效遍历。
内容的提问来源于stack exchange,提问作者Dhyey Shah
相关产品推荐
相关产品推荐

