【算法详解】区间内的质数和数字反转区间双解法暴力枚举埃氏筛优化一、题目描述给定一个整数n首先将n的数字反转得到新整数r。确定计算区间左边界为min\(n, r\)右边界为max\(n, r\)区间包含两端边界。要求返回该闭区间内所有质数的总和。质数定义大于 1且只能被 1 和自身整除的自然数。1.1 示例演示示例 1输入n 13输出132解析13 反转得到 31区间为 [13,31]。区间内质数13、17、19、23、29、31总和 131719232931 132。示例 2输入n 10输出17解析10 反转得到 1区间为 [1,10]。区间内质数2、3、5、7总和 17。示例 3输入n 8输出0解析8 反转仍为8区间为 [8,8]8不是质数总和为0。1.2 题目约束1 \lt; n \lt; 1000数据范围较小暴力解法完全可行同时可通过埃氏筛法做预处理优化适合算法入门学习。二、解题核心流程本题解题分为三大核心步骤所有解法均遵循该流程数字反转将输入整数 n 反转得到 r确定区间计算区间左右边界 L min(n, r)R max(n, r)区间质数求和遍历 [L, R]筛选所有质数并累加求和三、解法一暴力枚举法基础新手版3.1 算法思路拆解为三个独立函数实现逻辑清晰、易于理解反转数字函数通过取余、整除运算逐位反转数字质数判断函数对单个数字 k遍历 2~√k 判断是否为质数优化冗余循环区间求和遍历区间所有数字判断质数并累加质数判断优化点无需遍历到 k-1只需遍历到k\sqrt{k}k​若区间内无因数则为质数。3.2 完整代码实现classSolution:defsumOfPrimesInRange(self,n:int)-int:# ©leetcode# 步骤1反转数字n得到rdefreverse_num(x):res0whilex0:resres*10x%10xx//10returnres# 步骤2判断单个数字是否为质数defis_prime(x):# 小于2一定不是质数ifx2:returnFalse# 2是唯一偶质数ifx2:returnTrue# 偶数直接排除ifx%20:returnFalse# 遍历3到根号x步长2foriinrange(3,int(x**0.5)1,2):ifx%i0:returnFalsereturnTrue# 步骤3确定区间边界rreverse_num(n)Lmin(n,r)Rmax(n,r)# 步骤4遍历区间累加质数和prime_sum0fornuminrange(L,R1):ifis_prime(num):prime_sumnumreturnprime_sum3.3 测试代码if__name____main__:solSolution()# 官方示例测试print(sol.sumOfPrimesInRange(13))# 输出 132print(sol.sumOfPrimesInRange(10))# 输出 17print(sol.sumOfPrimesInRange(8))# 输出 0# 自定义测试案例print(sol.sumOfPrimesInRange(2))# 输出 2print(sol.sumOfPrimesInRange(21))# 反转12区间[12,21] 质数13,17,19 和为493.4 复杂度分析时间复杂度O\(\(R\-L\1\)\*√R\)区间内每个数需要根号级别的质数判断空间复杂度O\(1\)仅使用常数额外空间本题 n≤1000最大区间不超过 [1,1000]暴力解法效率完全达标。四、解法二埃氏筛法预处理优化版4.1 算法思路埃拉托斯特尼筛法埃氏筛是质数区间求和的最优解法核心思想先预处理标记所有质数再直接查表求和。根据题目最大范围 1000预处理出 0~1000 所有数字的质数标记数组预先计算质数前缀和数组可实现 O(1) 区间求和反转数字确定区间后直接通过前缀和公式计算区间质数总和前缀和求和公式sum\(L,R\) pre\_sum\[R\] \- pre\_sum\[L\-1\]4.2 完整代码实现classSolution:defsumOfPrimesInRange(self,n:int)-int:# ©leetcodeMAX_NUM1000# 1.埃氏筛预处理质数标记is_prime[True]*(MAX_NUM1)is_prime[0]is_prime[1]Falseforiinrange(2,int(MAX_NUM**0.5)1):ifis_prime[i]:# 标记i的所有倍数为非质数forjinrange(i*i,MAX_NUM1,i):is_prime[j]False# 2.预处理质数前缀和数组pre_sum[0]*(MAX_NUM1)total0foridxinrange(MAX_NUM1):ifis_prime[idx]:totalidx pre_sum[idx]total# 3.反转数字defreverse_num(x):res0whilex0:resres*10x%10xx//10returnres# 4.确定区间并计算结果rreverse_num(n)Lmin(n,r)Rmax(n,r)returnpre_sum[R]-pre_sum[L-1]4.3 测试代码if__name____main__:solSolution()# 官方示例测试print(sol.sumOfPrimesInRange(13))# 132print(sol.sumOfPrimesInRange(10))# 17print(sol.sumOfPrimesInRange(8))# 0# 边界测试print(sol.sumOfPrimesInRange(1))# 0print(sol.sumOfPrimesInRange(997))# 最大三位数质数测试4.4 分步逻辑解析以输入n13为例预处理完成后数组标记 0~1000 所有质数同时生成前缀和数组反转数字 13 得到 31区间 [13,31]通过前缀和计算pre_sum[31] - pre_sum[12] 132直接得出结果该解法将多次质数判断转为一次预处理查询效率极致优化。4.5 复杂度分析预处理时间复杂度O\(n log log n\)埃氏筛经典复杂度仅执行一次单次查询时间复杂度O\(1\)查表即可得出结果空间复杂度O\(1000\)固定大小数组可视为常数空间 O(1)五、两种解法对比总结解法时间效率空间开销优点适用场景暴力枚举法较慢区间越大越慢O(1) 无额外空间逻辑直白、代码简单、新手易理解单次查询、数据量极小埃氏筛优化法一次预处理永久O(1)查询固定常数空间效率极高适合多次查询多次调用、数据范围固定场景六、核心知识点与避坑指南6.1 数字反转要点无需处理前导零例如 n10反转过程10→01最终结果为1代码中整除取余逻辑会自动舍弃前导零无需额外处理。6.2 质数判断避坑0 和 1不是质数2 是唯一的偶数质数大于2的偶数全部非质数可直接跳过减少循环次数6.3 区间求和避坑区间必须包含左右边界循环范围为range\(L, R\1\)不可遗漏右边界。七、拓展极简优化暴力写法提供一份精简版代码保留核心逻辑适合刷题快速ACclassSolution:defsumOfPrimesInRange(self,n:int)-int:# 反转数字r,tmp0,nwhiletmp:rr*10tmp%10tmp//10L,Rmin(n,r),max(n,r)# 质数求和res0fornuminrange(L,R1):ifnum2:continueflagTrueforiinrange(2,int(num**0.5)1):ifnum%i0:flagFalsebreakifflag:resnumreturnres