置頂成品：在這里面，我一直是思考的，如果有特殊情況，會怎樣，于是按著特殊情況去優(yōu)化提升效率，結(jié)果卻是整體效率下降，于是兩個思路：
1、保證特殊情況的優(yōu)化，去忍受整體效率
2、保證整體效率，忍受特殊情況
好累，上午就得出的這個結(jié)果，因為如果再去做特殊情況的優(yōu)化的話，因為復(fù)雜度問題，可能會產(chǎn)生眾多的bug，這是最頭疼的一件事。
所以懶惰的我選擇… 搞一搞其他問題吧！把質(zhì)數(shù)庫加入到目前最通用的算法中！說實(shí)話，不想放棄！雖然耗了好長時間在這個上面了，比上一次的浮點(diǎn)數(shù)優(yōu)化層次太深了！

我剛才搜了下判斷一個數(shù)是否是素數(shù)的算法，涉及到了太多高等數(shù)學(xué)的知識，我放棄思考了。就這樣吧！

簡單單次開方法：

def 約數(shù)(n):if n==1:return 1y=[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

單次開方增強(qiáng)：從小到的尋找質(zhì)數(shù)，同時生成對應(yīng)約數(shù)組，循環(huán)生成直至新的目標(biāo)數(shù)不再包含該質(zhì)數(shù)。尋找更大的質(zhì)數(shù)。思路雖然簡單，但是期間遇上更多的問題，各種debug和優(yōu)化后，看代碼沒那么容易理解思路，而我剛才嘗試841，居然沒有之前的一個算法快，雖然841是一種特例吧！看來還是需要更加優(yōu)化

def Factor(n):if n==1:return [1]y=[]s=2while 1:yf=[]for i in range(s,int(t:=n**0.5)):if n/i%1==0:z=ibreakelse: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 yelse:z=int(n)yf.append(z)n=n/zfor i in y:yf.append(i*z)y+=yfwhile 1:if (t:=n/z)%1==0:n=tyt=[]for i in yf:yt.append(i*z)y+=ytyf=yt[:]elif n==1:y.append(1)y.sort()return yelse:breaks=z+1 %%timeit def Factor(n):if n==1:return [1]y=[]t=nwhile 1:if (t:=t**0.5)%1!=0:tm=int(t)t=int(t**2+0.1)breaks=2while 1:yf=[]for i in range(s,int(tm:=t**0.5)):if n/i%1==0:z=ibreakelse: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 yelse:z=int(n)yf.append(z)n=n/zfor i in y:yf.append(i*z)y+=yfwhile 1:if (t:=n/z)%1==0:n=tyt=[]for i in yf:yt.append(i*z)y+=ytyf=yt[:]elif n==1:y.append(1)y.sort()return yelse:breaks=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

這個加進(jìn)去之后，會涉及到更多的問題，一時很難解決，更適合最初的一個質(zhì)數(shù)組合法。

for i in range(800,900):
簡單版：505 μs ± 3.61 μs
加強(qiáng)版：552 μs ± 10.7 μs
循環(huán)加強(qiáng)版：535 μs ± 13.8 μs
之前的質(zhì)數(shù)庫版：737 μs ± 10.4 μs
之前的無質(zhì)數(shù)庫：762 μs ± 10.8 μs

10800,10900：
1.43 ms ± 12.4 μs
874 μs ± 34.5 μs
945 μs ± 16.1 μs
1.06 ms ± 15.8 μs
1.38 ms ± 32.7 μs
雖然看到小數(shù)量級時，仍未壓過簡單版，但是差距不大
但是大數(shù)量級時，是目前最快的了

t=nwhile 1:if (t:=t**0.5)%1!=0:tm=int(t)t=int(t**2+0.1)breaks=2while 1:yf=[]for i in range(s,int(tm:=t**0.5)):

修改版我是把之前的多次開方搬到了這里，目的是更加的減少無端的消耗，主要是當(dāng)目標(biāo)數(shù)是個質(zhì)數(shù)時！在小數(shù)量級時，這個功能負(fù)優(yōu)化，但是在大的數(shù)量級時，能減少目標(biāo)數(shù)是質(zhì)數(shù)時，一個指數(shù)級的運(yùn)算時長！明天繼續(xù)改！將三個方法的步驟完全模塊化列出，各個優(yōu)點(diǎn)整合起來！

我卸載blink上了，結(jié)果PC端無法看，坑！
我嘗試使用：

來判斷目標(biāo)數(shù)是否應(yīng)該開方，結(jié)果很無語，先上結(jié)果！
for i in range(10600,10900):
Factor(i)
未添加：2.59 ms
添加if個位數(shù)判斷：2.31 ms
完全不做開方：2.13 ms
也就是說完全不做總的來說效率更高！只能說純質(zhì)數(shù)與if之間的比例。
另外如果把if加入到每次循環(huán)結(jié)果的目標(biāo)數(shù)上，耗時更長，雖然這個點(diǎn)子單純的好，但是加進(jìn)去就不好了。
帶入997：很遺憾，第一次不做任何處理，效率最高，因為內(nèi)部同時做了個處理。
但如果帶入994009：未經(jīng)預(yù)先開放處理的123 μs ，開放處理的6.05 μs，所以還是有必要預(yù)先處理的，頂多是個取舍的問題，至于內(nèi)部的每次循環(huán)，例如2*61*61=7442，這個是需要內(nèi)部多次開方提升效率的。
但經(jīng)過幾次范圍測試，總之這些都是特例，特例到多做一次處理，整體耗時都會增加！
而這里面最核心最有用的就是一次開方
------------------------------歷史------------------------------
這個歷史比較坑，自以為是的用不斷開放法找到無法再開方的目標(biāo)，再找到質(zhì)數(shù)因子，再組合成約數(shù)組，以及引進(jìn)了質(zhì)數(shù)庫。質(zhì)數(shù)庫這個我將嘗試加入到上面的方法中，求約數(shù)仍在繼續(xù)！

如果使用一個質(zhì)數(shù)庫去優(yōu)化當(dāng)前算法，那么第一個問題，選擇多大的質(zhì)數(shù)庫，假設(shè)選擇1000以內(nèi)的質(zhì)數(shù)，那么他的適用范圍就是1000**2，即1000000 100W。

測試：
1000000的元組，內(nèi)存占用8000024字節(jié)，程序占用43516K，寫入文件的話，7.52MB，記事本打開很耗時。那么生成庫的大小將以記事本打開速度衡量。
當(dāng)生成1W的元組，記事本大小在60KB，大概60K個字符時，是秒開的。
但我們其實(shí)也根本用不到這個大的元組也未曾可知。而1W時，內(nèi)存占用是常規(guī)狀態(tài)，并沒有顯示出多么的大。那么從元組的對比效率上看呢。例如10元素的元組和多少個元素的元組，效率是差不多的。

等等，我創(chuàng)建了各種組合

a=tuple(range(1000000)) b=tuple(range(1000)) c=(999,) l=list(range(1000)) s=set(range(1000))999 in a

其中元組和列表都是線性搜索的，效率都一樣，而且不高
13.7 μs ± 60 ns
但是集合結(jié)果就很快
61.1 ns ± 1.47 ns
但是如果要順序運(yùn)算的話，就又不能用到集合
也就是說集合僅僅是用來判斷要運(yùn)算的數(shù)是否在質(zhì)數(shù)庫內(nèi)的方法
而且生成這些組合也是需要大量的耗時的
我直接賦值長度為1000的一個元組和一個集合，耗時21 μs
元組19.2 ns 集合21.5 μs 好吧，我錯了！
這樣的話，我只需要優(yōu)化元組的搜索算法即可，集合計算包含是快，但是生成較慢
那么現(xiàn)在確定，僅使用元組來進(jìn)行運(yùn)算

另

s=set(a) #14.4 μs a=tuple(s) #5.9 μs

比從源代碼賦值要快些

但，其實(shí)數(shù)字狀態(tài)下，for i in s的結(jié)果也是順序的。

于是這里考慮的還是質(zhì)數(shù)庫需要多大的問題，而且如果使用集合搜索的話，集合由元組生成而非手動賦值。

道理是這個道理，還是試一下看看吧，例如1000內(nèi)的質(zhì)數(shù)就100多個，生成組合數(shù)據(jù)耗時，10000個的生成組合數(shù)據(jù)耗時。無庫的算法在10W左右平均耗時是21μs，如果耗時過長，就劃不來了，就是反優(yōu)化！

z=[] for i in range(2,1000):for j in range(2,i):if i/j%1==0:breakelse: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以內(nèi)的質(zhì)數(shù)庫
耗時9.72 ms ± 145 μs
手動賦值為元組：19.3 ns
手動賦值為集合：3.99 μs
元組轉(zhuǎn)換為集合：3.34 μs
手動賦值為列表：926 ns
列表轉(zhuǎn)換為集合：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
既然庫是預(yù)置的，那么段我們也要預(yù)置下

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:returnc+=1fm(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, 20: 73, 41: 181, 62: 307, 83: 433, 104: 571, 125: 701, 146: 853, 167: 997}
分段后，更方便對比目標(biāo)數(shù)是否在范圍之內(nèi)，即目標(biāo)是否是范圍之內(nèi)的質(zhì)數(shù)，其他情況就是目標(biāo)在范圍之外，目標(biāo)是范圍內(nèi)的非質(zhì)數(shù)
if 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 k

200μs

997：
無庫 5.52 μs 2：1.6 μs
有庫分段 1.53 μs 2：1.14 μs 71：1.43 μs
有庫in 2.81 μs 2：244 ns 71：528 ns
算法2 4.57 μs 2：883 ns
在分段上，這樣不行，需要優(yōu)先算前邊的，這樣分段才有意義

小數(shù)優(yōu)先：71：516 ns 2：243 ns 997：2.55 μs
如果用算法代替預(yù)置段，這個之后再說，首先引入庫的目的本不是預(yù)置段，而是更快的找到基數(shù)質(zhì)數(shù)

%%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)break

24.7 μs ± 1.4 μs
寫是寫出來了，但是結(jié)果著實(shí)不正常，經(jīng)過篩查，問題出在這了

%%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

雖然允許是有差距，但關(guān)鍵不在運(yùn)行，在我之前苦惱的一個問題，如何截斷，例如：
841：292
質(zhì)數(shù)庫：3.73 μs
未優(yōu)化：2.88 μs
因為未優(yōu)化的，它采用的是290.5去求質(zhì)數(shù)

那就用最簡單的方法截斷試試！
先算一下，for元組，一個循環(huán)10ns，if也是10ns，試試吧，看看是否有提升
不方便，如果使用if，break截斷的話，就是雙循環(huán)，外層循環(huán)無法使用簡單的方法跳出，無奈寫了個內(nèi)置函數(shù)，使用return跳出
3.38 μs ± 110 ns
稍有提升，未到未優(yōu)化的狀態(tài)

def 約數(shù)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 1t=nwhile 1:if (t:=t**0.5)%1!=0:tm=int(t)t=int(t**2+0.1)breakz=[]def 質(zhì)數(shù)(t):while 1:if t==1:returnif (tm:=t**0.5//1)==1:z.append(t)returnfor i in k:if i<=tm:if t/i%1==0:z.append(i)breakelse:if tm>997:for i in (998,int(tm)+1):if t/i%1==0:z.append(i)breakelse:z.append(t)returnwhile 1:if (t:=t/i)%1!=0:t=int(t*i+0.1)break質(zhì)數(shù)(t)y=[]for i in z:zy=[]t=nii=izy.append(i)t=t/iwhile 1:if (t:=t/i)%1==0:zy.append(ii:=ii*i)else:breakfor j in y:t=n/jii=1while 1:if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))else:breaky+=zyy.append(1)y.sort()return y

我盡力了

------------------------------------------------以下是無質(zhì)數(shù)庫------------------------------------------------

def 約數(shù)算法1(n):if n==1:return 1t=nwhile 1:if (t:=t**0.5)%1!=0:tm=int(t)t=int(t**2+0.1)breakz=[]while 1:if t==1:breakif tm==1:z.append(t)breakfor i in range(2,tm):if (t/i)%1==0:t=t/iz.append(i)breakelse:if (t/tm)%1==0:i=tmz.append(tm)else:z.append(t)breakwhile 1:if (t:=t/i)%1!=0:t=int(t*i+0.1)tm=int(t**0.5)breaky=[]for i in z:zy=[]t=nii=izy.append(i)t=t/iwhile 1:if (t:=t/i)%1==0:zy.append(ii:=ii*i)else:breakfor j in y:t=n/jii=1while 1:if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))else:breaky+=zyy.append(1)y.sort()return ydef 約數(shù)算法2(n):if n==1:return 1y=[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是很久前就想好了的，并一直在用，但是剛才批量過數(shù)據(jù)debug的時候，發(fā)現(xiàn)算法2有致命bug，現(xiàn)在兩個算法結(jié)果一致了，大概都沒問題了！

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
數(shù)值在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

其實(shí)我還有個思路來著，應(yīng)該能更加優(yōu)化下質(zhì)數(shù)組合。明日繼續(xù)優(yōu)化

算法2是簡單的一次開平方思路，算法1是在其基礎(chǔ)上各種腦洞，最后總結(jié)算是質(zhì)數(shù)法。

小數(shù)值下，算法2可能更快，畢竟結(jié)構(gòu)復(fù)雜性在那，但是大數(shù)值下是算法1更快！

--------------------------------------------------------以下是歷史記錄--------------------------------------------------------

之所以要用質(zhì)數(shù)法，就是為了彌補(bǔ)可以再次開平方的情況，那么就假設(shè)做到極致，用2的平方測試，再用7的平方測試。
4：
2.19 μs ± 63.4 ns
1.11 μs ± 9.49 ns

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

至此，可以看到在大步進(jìn)的質(zhì)數(shù)下，兩段開方，這個長代碼的效率就趕上來了。

再舉個極端的例子，例如兩個大質(zhì)數(shù)相乘！

989=23*43
10.4 μs ± 99.6 ns
4.62 μs ± 133 ns

我貌似想到一個更好的思路，聰明的人肯定一開始就能想到，撞墻。
如果我不采用質(zhì)數(shù)拼，或者用更好的拼法呢倒三角形，或者過程合一

-----------------------------------------------以下是歷史文檔，可略--------------------------------------------

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
修改后有稍許提升，但是結(jié)構(gòu)并沒有大的優(yōu)化

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

其實(shí)我對這個思路還是有自信的，看看哪里還能優(yōu)化下

---

代碼還沒完成，就發(fā)現(xiàn)一個問題，記錄下

# from random import randint #生成一個數(shù)，求他的約數(shù) # n=randint(1,1000) n=2251875390625 #定義一個變量 def 求約數(shù)(n):t=nt=n#開平方縮減運(yùn)算量while 1:if (t:=t**0.5)%1==0:nt=telse:break#定義質(zhì)數(shù)集合#!!!這個def之后嘗試寫成while，試一下效率是否改變z=[]def 求質(zhì)數(shù)(nt):for i in range(2,nt):if nt/i%1==0:z.append(i)breakelse:z.append(nt)returnt=nt=nt/iwhile 1:if (t:=t/i)%1!=0:breaknt=t求質(zhì)數(shù)(int(nt))求質(zhì)數(shù)(int(nt)) 求約數(shù)(n)

目前以完成求質(zhì)數(shù)步驟，但發(fā)現(xiàn)耗時已經(jīng)超了

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()

之前運(yùn)行的是n=996
12 μs ± 250 ns
6.1 μs ± 162 ns
耗時近翻倍
于是這次我找了個大數(shù)n=2251875390625
3.64 μs ± 64.6 ns
190 ms ± 3.22 ms

超逆襲，我沒想到1225其實(shí)可以開平方成35的，但可以得出，當(dāng)進(jìn)入2步驟時，數(shù)量一樣的話，加強(qiáng)優(yōu)化的效率沒小優(yōu)化的效率高。主要在求質(zhì)數(shù)部分，這里盡可能的再優(yōu)化下，或者可以與之后的質(zhì)數(shù)組合銜接以節(jié)省重復(fù)運(yùn)算。

小優(yōu)化如果做二段開平方的話，會發(fā)生問題的。所以才想到用質(zhì)數(shù)拼約數(shù)，但這功能又會用到組合這個不大不小的話題！

%%timeit n=989 def 約數(shù)(n):if n==1:return 1t=nt=nwhile 1:if (t:=t**0.5)%1==0:nt=telse:breaky=[]if nt==n:while 1:zy=[]for i in range(2,int(nt)):if nt/i%1==0:zy.append(i)breakelse:zy.append(int(nt))i=zy[-1]nt=nt/iit=iwhile 1:if (t:=nt/i)%1==0:nt=tzy.append(it:=it*i)else:breakfor j in y:it=1t=nt=t/jwhile 1:if (tt:=t/i)%1==0:t=ttzy.append(j*(it:=it*i))else:breaky+=zyif nt==1:breaky.append(1)y.sort()return y y=約數(shù)(n)

這個程序做了一下改動，是針對第一次開方不是整數(shù)的情況，且將它稱之為情況1，而本文最開始的文章是情況2。情況1是針對情況2的如上描述做的調(diào)整
989：
10.5 μs ± 184 ns
10.4 μs ± 99.6 ns

12288：
11.5 μs ± 387 ns
19 μs ± 494 ns

1228：
40.9 μs ± 1.02 μs
42.4 μs ± 492 ns
什么鬼，這個絕對不值
一次開方法：5.46 μs ± 120 ns
[1, 2, 4, 307, 614, 1228]
屬于雙質(zhì)數(shù)，而且是很小的質(zhì)數(shù)和很大的質(zhì)數(shù)的搭配
還是說我的這個長代碼有bug

長代碼耗時

• 開方：490 ns
• 質(zhì)數(shù)：38.6 μs
• 結(jié)果：42.4 μs
  所以問題出在了取質(zhì)數(shù)這上面

新思路，既然一次開方法更快，何不借鑒

%%timeit n=1228 def 約數(shù)(n):if n==1:return 1t=nwhile 1:if (t:=t**0.5)%1!=0:tm=int(t)t=int(t**2+0.1)breakz=[]while 1:for i in range(2,tm):if (t/i)%1==0:t=t/iz.append(i)breakelse:z.append(t)breakwhile 1:if (t:=t/i)%1!=0:t=int(t*i+0.1)tm=int(t**0.5)breaky=[]for i in z:zy=[]t=nii=izy.append(i)t=t/iwhile 1:if (t:=t/i)%1==0:zy.append(ii:=ii*i)else:breakfor j in y:t=n/jii=1while 1:if (t:=t/i)%1==0:zy.append(j*(ii:=ii*i))else:breaky+=zyy.append(1)y.sort()return y 約數(shù)(n)

6.65 μs ± 103 ns
近乎完成品了

總結(jié)

以上是生活随笔為你收集整理的python - 求约数 质数法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。