欧拉计划12题优化:Python求因数个数的两种算法时间反常疑问
我的因数计数算法优化异常
我已经求解了欧拉计划第12题,并尝试优化解法。本次优化的核心模块是因数个数计算逻辑。
我原本以为自己写的第一套算法会比第二套慢,但实际运行结果恰好相反,无法理解其中原因。
第一套算法:常规遍历法
规则:遍历终止值为n的平方根
from math import sqrt def get(n): count = 0 limit = sqrt(n) for i in range(1,int(limit)+1): if n%i==0: count+=2 if limit.is_integer(): return count-1 return count
第二套算法:素因数分解法
逻辑:先分解素因数得到每个素因子的指数,结合因数个数公式计算;实现时用了6m±1形式的素数性质来提升计算速度,但实际运行依然更慢
def Get_Devisors_Amount(n):#Prime factorization if n <=1: return 1 dcount = 1 count = 0 while n%2==0: count+=1 n//=2 dcount*=(count+1) count = 0 while n%3==0: count+=1 n//=3 dcount*=(count+1) i = 1#count for the form of primes 6n+-1 while n!=1: t = 6*i+1 count = 0 while n%t==0: count+=1 n//=t dcount*=(count+1) t = 6*i-1 count = 0 while n%t==0: count+=1 n//=t if count!=0: dcount*=(count+1) i+=1 if dcount==1: return 2# n is a prime return dcount
测试方式与结果
测试代码:
import time start = time.time() for i in range(1,1000): get(i) print(time.time()-start) start = time.time() for i in range(1,1000): Get_Devisors_Amount(i) print(time.time()-start)
运行输出:
get函数耗时:0.00299835205078125Get_Devisors_Amount函数耗时:0.009994029998779297
核心疑问
尽管我使用了相关数学性质和公式来降低搜索耗时,第一套方法的运行速度反而更快,能否解释背后的原因?
原因分析
速度差异完全是小数字测试场景下的固定开销和实现效率共同导致的,和理论渐近复杂度无关,核心原因有三点:
1. 测试规模太小,理论复杂度优势完全被常数开销抵消
两个算法的渐近时间复杂度确实是素因数分解法更优,但这一优势只有处理大数字时才能体现:
- 对1~999的小数字,遍历法最多只需要循环31次(因为sqrt(999)≈31.6),循环体只有
取模+计数器自增两个操作,Python解释器执行这类简单循环的效率极高。 - 素因数分解法虽然只需要遍历6m±1的候选数(比全遍历少2/3的测试次数),但每一次循环的操作成本远高于遍历法:
- 每轮要做两次取模运算(分别测试6i+1和6i-1)
- 要重复初始化
count变量、执行额外的分支判断
这些固定操作的开销,远大于减少遍历次数带来的收益。
2. 遍历法的执行流更符合Python的优化特性
Python的range生成的连续整数序列是经过底层优化的,连续的循环遍历在解释器中执行的字节码指令数量远少于素因数分解法的零散分支操作。小整数的取模运算在Python中走快速路径,没有额外的类型检查开销,进一步放大了遍历法的速度优势。
3. 素因数分解法的实现存在冗余操作
- 对
6i+1的分支,没有判断是否真的整除就直接执行dcount *= (count+1):如果不能整除,count为0,相当于乘1,属于无意义的乘法运算,每轮循环都会额外执行一次。 - 没有加
t > sqrt(n)的提前终止判断:当测试的除数已经超过当前剩余n的平方根时,就不需要继续遍历了,但当前实现直到n==1才退出,对素数输入会多做十几轮无效循环,进一步增加开销。
素因数分解法的速度优势什么时候会体现?
当计算的n超过10^6之后,遍历法需要循环到1000次以上,素因数分解法的循环次数优势才会超过固定开销。如果搭配提前生成的素数筛预计算素数列表,跳过所有非素数的测试项,速度还能进一步提升。
内容的提问来源于stack exchange,提问作者Noa
相关产品推荐
相关产品推荐

