python - 求约数 质数法
核心产品：在这一块里一直都在琢磨各种方案和技术路线，在遇到特殊场景时会如何处理？最终发现两种思路：一种是专注于解决特殊场景的问题而忍耐整体性能；另一种是优先保证整体性能水平的同时合理处理特殊场景的情况
我刚才了解了一下判断一个数是否为素数的相关算法，在这个过程中需要用到许多高等数学的知识内容暂时搁置了思考。
简单单次开方法：
def 约数(n):
if n==1:return 1
y=[1,n]
if (m:=n**0.5)%1==0:
m=int(m)
y.append(m)
else:m=int(m+1)
for i in range(2,m):
if n/i%1==0:
y.append(i)
y.append(int(n/i))
y.sort()
return y单次开方增强：从小到大的质因数分解过程中同时生成对应的约数对，并不断循环生成直至新的目标不再包含该质因数。整个思路看似简单但在实现过程中遇到了诸多挑战经过一系列调试与优化后代码实现起来依然较为复杂难以直观理解整个思路。测试发现841这个特例运行效率甚至不比之前的算法高这提示我们需要进一步优化算法性能以提升整体效率。
def Factor(n):
if n==1:return [1]
y=[]
s=2
while 1:
yf=[]
for i in range(s,int(t:=n**0.5)):
if n/i%1==0:
z=i
break
else:
if t%1==0:
z=int(t)
elif n/(t//1)%1==0:
z=int(t//1)
for i in y:
yf.append(i*z)
y+=yf+[z]
yf=[]
z=int(n/(t//1))
for i in y:
yf.append(i*z)
y+=yf+[z]
y.sort()
return y
else:z=int(n)
yf.append(z)
n=n/z
for i in y:
yf.append(i*z)
y+=yf
while 1:
if (t:=n/z)%1==0:
n=t
yt=[]
for i in yf:
yt.append(i*z)
y+=yt
yf=yt[:]
elif n==1:
y.append(1)
y.sort()
return y
else:break
s=z+1 %%timeit
def Factor(n):
if n==1:return [1]
y=[]
t=n
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break
s=2
while 1:
yf=[]
for i in range(s,int(tm:=t**0.5)):
if n/i%1==0:
z=i
break
else:
if t%1==0:
z=int(t)
elif n/(t//1)%1==0:
z=int(t//1)
for i in y:
yf.append(i*z)
y+=yf+[z]
yf=[]
z=int(n/(t//1))
for i in y:
yf.append(i*z)
y+=yf+[z]
y.sort()
return y
else:z=int(n)
yf.append(z)
n=n/z
for i in y:
yf.append(i*z)
y+=yf
while 1:
if (t:=n/z)%1==0:
n=t
yt=[]
for i in yf:
yt.append(i*z)
y+=yt
yf=yt[:]
elif n==1:
y.append(1)
y.sort()
return y
else:break
s=z+1
for i in range(800,900):
Factor(i) if (o:=n%10)==1 or o==3 or o==7 or o==9:
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break将加入这一项后
for i in range(800,999):
基本版本耗时约为5^{\text{百}}微秒\pm约4个\mus
增强版本耗时约为~\texttt{~}~约千五undredmicrosecond水平\pm约十一个microsecond
循环增强版本耗时约为五三五microsecond水平\pm约十三点八microsecond
旧的质数表辅助版本耗时约为七三七microsecond水平\pm约十点四microsecond
旧无质数表版本耗时约为七六二microsecond水平\pm约十点八microsecond
注意到在小数量级的情况下（如10800,10900），该性能表现未达到简单版的水平（例如：平均时间为约1.43毫秒±12.4微秒），但其与之相比仍具一定的竞争力（约为874微秒±34.5微秒）。然而，在大数量级测试中（如945微秒±16.1微秒），该方法的表现最为突出（约为1.06毫秒±15.8微秒），并显示出显著的优势（例如：与其他配置相比平均时间缩短约32.7微秒）。尽管如此，在小规模测试中其性能略逊于简单版方案（如：平均时间为约1.38毫秒±32.7微秒），但总体而言，在大多数场景下仍能提供较为理想的表现。
t=n
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break
s=2
while 1:
yf=[]
for i in range(s,int(tm:=t**0.5)):本次版本更新的主要改动包括将原有设计中的多次开方操作移至此处。其主要目的便是为了最大限度地减少不必要的资源消耗。这一特性尤其适用于当目标数值为质数的情况，在小规模计算场景下表现欠佳，在此处的大规模计算场景中，则能够有效降低当目标数值为质数时所需的计算时间指数级增长。明天继续改进算法性能并优化代码实现细节！将这三个方法的操作步骤进行模块化整合以提高代码可读性和维护性
我卸载blink上了，结果PC端无法看，坑！
我尝试使用：
为了判断目标数是否需要开平方以便提高效率 我们进行了多方面的测试并得出了以下结论：
具体来说就是 未做任何优化时耗时2.59 ms
通过引入个位数筛选机制 耗时减少至2.31 ms
完全不做开方处理的情况下 耗时进一步降至2.13 ms
由此可见 在不做任何优化的情况下效率相对较高 这一发现表明 筛选质数组的比例在整体性能提升中起到了关键作用
然而 如果将个位数筛选应用到每次循环的结果中 尽管这一策略在某些情况下看似合理 但在实际操作中却会导致额外的计算负担
值得指出的是 带入特定数值如997时 没有进行任何优化的情况所耗时间反而较长（约7442次运算） 这一现象令人意外
当采用一个质数集合来优化现有算法时，
首要考虑的问题是确定质数集合的规模。
决定选用哪些大小范围内的质数值。
假设选用小于等于\leqslant 5以内或\leqslant 5\times\text{ million}等特定值，
这将导致该算法的有效应用范围是约一百万次运算（即\approx\text{ million}）。
测试：
一百万个元组（即长度为一百万的数据结构），其内存占用约为8,192 KB（约8兆字节），程序运行占用了约43.5 MB内存空间，并将数据写入文件后占用了大约7.52 MB空间；由于使用记事本来记录数据会导致非常缓慢的操作速度。因此我们以记录操作的速度来评估生成库的整体规模（即所需存储空间）。
当生成数量为一千个元素（即k）的数据结构时，在存储量约为6万 KB左右（即大约6万字符的时候）完成操作的时间非常短暂；此时的数据结构读取速度达到了最优状态（即秒级）。
然而我们实际上并不需要如此庞大的数据结构来满足大多数应用场景的需求；而从数据结构对比效率的角度来看的话，则是小规模数据结构具有更好的性能表现——例如在包含十个元素的数据结构与某个数量级的数据结构之间进行比较时两者的表现基本相当一致
等等，我创建了各种组合
a=tuple(range(1000000))
b=tuple(range(1000))
c=(999,)
l=list(range(1000))
s=set(range(1000))
999 in a其中元组与列表均采用线性搜索策略，并未显示出效率差异
13.7\ \mu s \pm 60\ ns
相比之下，在集合上的运算速度非常快
61.1\ nanoseconds \pm 1.47\ ns
然而，在需要顺序运算的情况下，则无法直接利用集合特性
即集合仅用于判断待运算数是否存在于质数库中这一功能
而生成这些组合的过程则耗费大量时间
为了测试性能优化效果 我预先分配了一个长度为1000的元组及一个集合 结果耗时仅为21微秒
元组运行时间为19.2\ ns 集合运行时间却达21.5\ \mu s 哦 我弄错了单位！
由此可见 优化元组搜索算法将是更为有效的改进方向
即使集合判断本身较为高效 但在生成组合方面仍存在明显瓶颈
另
s=set(a) #14.4 µs
a=tuple(s) #5.9 µs比从源代码赋值要快些
但，其实数字状态下，for i in s的结果也是顺序的。
于是这里探讨的仍然是质数库需要解决的问题，并且如果采用集合搜索的方式，则该集合由元组构成而非人工赋值。
该问题本质上就是这个道理，请试着实际操作一下吧！比如在小于等于1000的整数中寻找质数数量大约有168个左右（注：具体数量根据实际情况确定），而生成所有可能的组合会产生较大的计算开销；非库存实现在处理接近十万的数据量时平均每秒只需21微秒左右（注：具体数值根据实际测试结果而定）。当计算时间超过预期后可能会导致整体效率下降。
z=[]
for i in range(2,1000):
for j in range(2,i):
if i/j%1==0:break
else:z.append(i)
print(len(z),z)168 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
1000以内的质数库
耗时9.72 ms ± 145 µs
手动赋值为元组：19.3 ns
手动赋值为集合：3.99 µs
元组转换为集合：3.34 µs
手动赋值为列表：926 ns
列表转换为集合：3.62 µs
果然集合还是过于耗时，先放弃。
997 in k：2.34 µs
k.contains(997)：2.43 µs
997 in k[-10:-1]：284 ns
997==k[-1]：62.5 ns
997==997：35 ns
len[k]：67.6 ns
既然库是预置的，那么段我们也要预置下
ml={0:2,167:997}
def fm(k,s,e,c=0):
m=s+int((e-s)/2)
ml[m]=k[m]
if c==2:return
c+=1
fm(k,s,m,c)
fm(k,m,e,c)
fm(k,0,167)
md={}
for i in sorted(ml):
md[i]=ml[i]
print(md){0: 2, ..., } 分组后使得更容易比较各区间的情况。
判断该目标是否属于区间内质数的问题。
当a大于等于1时运行pass操作的计算时间为35.2 ns。
in方法用于进行元素对比，在每次循环中所需的时间约为28ns。
%%timeit
def kk(t):
k=(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)
if t>=433:
if t>=701:
if t>=853:
if t in k[146:]:return [1,t]
else:
if t in k[125:146]:return [1,t]
else:
if t>=571:
if t in k[104:125]:return [1,t]
else:
if t in k[83:104]:return [1,t]
else:
if t>=181:
if t>=307:
if t in k[62:83]:return [1,t]
else:
if t in k[41:62]:return [1,t]
else:
if t>=73:
if t in k[20:41]:return [1,t]
else:
if t in k[:20]:return [1,t]
for i in k:
kk(i)平均耗时0.56µs…
%%timeit
for i in k:
i in k200µs
997号单元格（非缓存）的运行时间为5.52微秒。
带缓存的单元格分割（有缓存）运行时间分别为1.53微秒和...
带缓存的in指令运行时间为...。
在数据分割方面存在不足，在计算时应优先考虑前面的部分。
采用小数优先级的方式排序: 71: 516ns, 2: 243ns, 997: 2.55µs
%%timeit
k=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
t=997
z=[]
for i in k:
if t/i%1==0:
z.append(i)
break24.7 µs ± 1.4 µs
写是写出来了，但是结果着实不正常，经过筛查，问题出在这了
%%timeit
k=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
for i in k:
""3.28 µs
而相比
k为元组：1.99 µs ± 63.4 ns
k为集合：7.26 µs ± 75 ns
尽管存在性能上的差距，但关键在于算法的效率。在我之前遇到的一个问题是如何实现截断。841：29**2 质数库：3.73 µs 非优化版本运行时间较短 未优化：2.88 µs 因为未优化方法则利用29的平方根来判断质数
我们可以尝试采用最为基础的方法进行截断操作。为了验证这一猜想是否可行，在此我们进行了初步的时间估算：对于for元组结构来说，默认情况下每个循环所需时间为10ns左右（包括if条件判断以及break操作），那么这个简单的测试方案可能会带来多大的优化效果呢？
不幸地发现这一方法并不十分理想（就不太方便了）。由于在嵌套循环的情况下（即外层循环每次都需要调用break语句来终止内层循环），单纯依靠简单的for语句已经无法实现高效的退出机制（无奈只能调用内置函数并借助return机制来实现跳出操作）。
经过上述调整后的新版本运行时间显示为3.38 µs ± 110 ns（±符号表示测量误差范围），相比之前的基准值确实有所提升（稍有改善）。然而这仍然未能达到预期的最佳优化状态（未完成进一步优化方案的具体细节）。
def 约数1(n):
k=(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)
if n==1:return 1
t=n
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break
z=[]
def 质数(t):
while 1:
if t==1:return
if (tm:=t**0.5//1)==1:
z.append(t)
return
for i in k:
if i<=tm:
if t/i%1==0:
z.append(i)
break
else:
if tm>997:
for i in (998,int(tm)+1):
if t/i%1==0:
z.append(i)
break
else:
z.append(t)
return
while 1:
if (t:=t/i)%1!=0:
t=int(t*i+0.1)
break
质数(t)
y=[]
for i in z:
zy=[]
t=n
ii=i
zy.append(i)
t=t/i
while 1:
if (t:=t/i)%1==0:zy.append(ii:=ii*i)
else:break
for j in y:
t=n/j
ii=1
while 1:
if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))
else:break
y+=zy
y.append(1)
y.sort()
return y我尽力了
------------------------------------------------以下是无质数库------------------------------------------------
def 约数算法1(n):
if n==1:return 1
t=n
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break
z=[]
while 1:
if t==1:break
if tm==1:
z.append(t)
break
for i in range(2,tm):
if (t/i)%1==0:
t=t/i
z.append(i)
break
else:
if (t/tm)%1==0:
i=tm
z.append(tm)
else:
z.append(t)
break
while 1:
if (t:=t/i)%1!=0:
t=int(t*i+0.1)
tm=int(t**0.5)
break
y=[]
for i in z:
zy=[]
t=n
ii=i
zy.append(i)
t=t/i
while 1:
if (t:=t/i)%1==0:zy.append(ii:=ii*i)
else:break
for j in y:
t=n/j
ii=1
while 1:
if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))
else:break
y+=zy
y.append(1)
y.sort()
return y
def 约数算法2(n):
if n==1:return 1
y=[1,n]
if (m:=n**0.5)%1==0:
m=int(m)
y.append(m)
else:m=int(m+1)
for i in range(2,m):
if n/i%1==0:
y.append(i)
y.append(int(n/i))
y.sort()
return y算法2早在以前就已确定，并长期在使用中。但最近在进行数据批量处理时发现了算法2存在严重的缺陷，并经过修复后两个算法的输出结果一致了。
for i in range(100,200)
算法1：580 µs ± 19.2 µs
算法2：294 µs ± 6.5 µs
1000，1200
1.65 ms ± 16.5 µs
1.17 ms ± 15.5 µs
10000,10200
2.63 ms ± 77.1 µs
2.95 ms ± 79.8 µs
数值在10000级别时，才反超
100000,100200
4.34 ms ± 93.2 µs
8.4 ms ± 104 µs
196
5.99 µs
3.46 µs
1228
6.95 µs
5.68 µs
4096
6.33 µs
10.2 µs
其实我还有个思路来着，应该能更加优化下质数组合。明日继续优化
算法2基于一次开平方思路；在这一基础上进行多种创新性的想法；最终将被归类为质数法
小数值下，算法2可能更快，毕竟结构复杂性在那，但是大数值下是算法1更快！
--------------------------------------------------------以下是历史记录--------------------------------------------------------
质因数分解法得以应用的原因是为了消除在平方运算中可能出现的可逆性问题。为此我们假设尽可能地运用2²检验方法随后配合7²检验方法以确保算法的有效性与可靠性
计算得出结果如下：
耗时为2.19微秒±63.4纳秒
耗时为1.11微秒±9.49纳秒
16：
3.37 µs ± 87.1 ns
1.7 µs ± 29.6 ns
256：
5.15 µs ± 113 ns
3.9 µs ± 51.9 ns
65536：
9.07 µs ± 118 ns
32.7 µs ± 1.09 µs
49：
2.94 µs ± 109 ns
1.75 µs ± 5.55 ns
2401：
4.06 µs ± 54 ns
6.94 µs ± 268 ns
在此阶段的大质数环境下进行分段平方根运算后，在较长代码中实现了预期水平
再举个极端的例子，例如两个大质数相乘！
989=23*43
10.4 µs ± 99.6 ns
4.62 µs ± 133 ns
似乎想到了一个更优的方案。聪明的人通常会很快意识到这一点。
如果不使用质数编码法，则可能会遇到效率问题。
另一种方法是使用更高效的编码方式，并非倒置三角形。
或则将过程统一处理。
-----------------------------------------------以下是历史文档，可略--------------------------------------------
n=16
3.66 µs ± 51.5 ns
1.68 µs ± 12.3 ns
81:
4 µs ± 204 ns
2.26 µs ± 58.5 ns
61:
8.8 µs ± 186 ns
1.53 µs ± 10.1 ns
64:
5.21 µs ± 41.6 ns
2.54 µs ± 38.7 ns
256:
5.83 µs ± 46.9 ns
3.71 µs ± 116 ns
改：5.52 µs ± 239 ns
1225:
7.83 µs ± 64.3 ns
6.13 µs ± 134 ns
改：7.52 µs ± 188 ns
修改后有稍许提升，但是结构并没有大的优化
4096:
8.22 µs ± 102 ns
10.4 µs ± 193 ns
改：7.5 µs ± 97.9 ns
16384:
9.66 µs ± 124 ns
17.5 µs ± 195 ns
其实我对这个思路还是有自信的，看看哪里还能优化下
代码还没完成，就发现一个问题，记录下
# from random import randint
#生成一个数，求他的约数
# n=randint(1,1000)
n=2251875390625
#定义一个变量
def 求约数(n):
t=nt=n
#开平方缩减运算量
while 1:
if (t:=t**0.5)%1==0:nt=t
else:break
#定义质数集合
#!!!这个def之后尝试写成while，试一下效率是否改变
z=[]
def 求质数(nt):
for i in range(2,nt):
if nt/i%1==0:
z.append(i)
break
else:
z.append(nt)
return
t=nt=nt/i
while 1:
if (t:=t/i)%1!=0:break
nt=t
求质数(int(nt))
求质数(int(nt))
求约数(n)目前以完成求质数步骤，但发现耗时已经超了
n=2251875390625
y=[1,n]
if (m:=n**0.5%1)==0:y.append(m)
for i in range(2,int(n**0.5)):
if n/i%1==0:
y.append(i)
y.append(int(n/i))
y.sort()之前运行的是n=996
12 µs ± 250 ns
6.1 µs ± 162 ns
耗时近翻倍
于是这次我找了个大数n=2251875390625
3.64 µs ± 64.6 ns
190 ms ± 3.22 ms
这个发现让我感到意外的是原来1225=35^2这一事实。然而进一步分析表明，在处理数量相等的情况下（即进入第二步的时候），采用大规模优化方法所带来的效率提升要明显高于小规模优化方法的效果。对于质数求解的部分，则需要尽可能地进行进一步优化工作或者尝试将其与其他质因数分解步骤结合使用以减少冗余计算。
一个小优化如果进行二段开平方的话,会出现问题.因此想到了分解质因数的方法.但是这个方法会被用来计算组合这样的中等规模的问题!
%%timeit
n=989
def 约数(n):
if n==1:return 1
t=nt=n
while 1:
if (t:=t**0.5)%1==0:nt=t
else:break
y=[]
if nt==n:
while 1:
zy=[]
for i in range(2,int(nt)):
if nt/i%1==0:
zy.append(i)
break
else:zy.append(int(nt))
i=zy[-1]
nt=nt/i
it=i
while 1:
if (t:=nt/i)%1==0:
nt=t
zy.append(it:=it*i)
else:break
for j in y:
it=1
t=n
t=t/j
while 1:
if (tt:=t/i)%1==0:
t=tt
zy.append(j*(it:=it*i))
else:break
y+=zy
if nt==1:break
y.append(1)
y.sort()
return y
y=约数(n)该程序进行了必要的修改。该修改主要针对开方结果非整数的情况，并将其定义为情况1；而最初的文章属于情况2。
12288：
11.5 µs ± 387 ns
19 µs ± 494 ns
在数值为1228的情况下
长代码耗时
- 开方：490 ns
- 质数：38.6 µs
- 结果：42.4 µs
所以问题出在了取质数这上面
新思路，既然一次开方法更快，何不借鉴
%%timeit
n=1228
def 约数(n):
if n==1:return 1
t=n
while 1:
if (t:=t**0.5)%1!=0:
tm=int(t)
t=int(t**2+0.1)
break
z=[]
while 1:
for i in range(2,tm):
if (t/i)%1==0:
t=t/i
z.append(i)
break
else:
z.append(t)
break
while 1:
if (t:=t/i)%1!=0:
t=int(t*i+0.1)
tm=int(t**0.5)
break
y=[]
for i in z:
zy=[]
t=n
ii=i
zy.append(i)
t=t/i
while 1:
if (t:=t/i)%1==0:zy.append(ii:=ii*i)
else:break
for j in y:
t=n/j
ii=1
while 1:
if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))
else:break
y+=zy
y.append(1)
y.sort()
return y
约数(n)6.65 µs ± 103 ns
近乎完成品了