在Python中查找數字的所有因子的最有效方法是什么？有人可以向我解釋一種在Python（2.7）中查找數字的所有因子的有效方法嗎？我可以創建算法來完成這項工作，但我認為編碼很差，并且執行大量數據的結果需要很長時間。
3 回答
尚方寶劍之說
TA貢獻1788條經驗 獲得超4個贊
from functools import reducedef factors(n): return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
這將很快返回所有因素n。
為什么平方根為上限？
sqrt(x) * sqrt(x) = x。因此，如果兩個因素相同，它們都是平方根。如果你將一個因子做大，你必須使另一個因子變小。這意味著兩者中的一個總是小于或等于sqrt(x)，因此您只需要搜索到該點以找到兩個匹配因子中的一個。然后你可以x / fac1用來獲取fac2。
該reduce(list.__add__, ...)走的小名單[fac1, fac2]，并在一個長長的清單一起加入他們。
在[i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0返回兩個因素，如果當你除以其余n由較小的一個是零（它并不需要檢查較大的一個過;它只是獲取除以n通過較小的一個）
該set(...)在外面擺脫重復，這僅發生于完美的正方形。因為n = 4，這將返回2兩次，所以set擺脫其中一個。
鳳凰求蠱
TA貢獻1825條經驗 獲得超4個贊
通過檢查奇偶校驗，可以使任意奇數的運行時間縮短約50％。由于奇數的因子本身總是奇數，所以在處理奇數時沒有必要檢查它們。
我剛剛開始自己解決Project Euler謎題。在某些問題中，在兩個嵌套for循環內部調用除數檢查，因此該函數的性能至關重要。
將這一事實與agf優秀的解決方案相結合，我最終得到了這個功能：
from math import sqrtdef factors(n): step = 2 if n%2 else 1 return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))
但是，對于較小的數字（?<100），此更改的額外開銷可能會導致函數花費更長時間。
我跑了一些測試來檢查速度。以下是使用的代碼。為了產生不同的圖，我相應地改變了X = range(1,100,1)。
import timeitfrom math import sqrtfrom matplotlib.pyplot import plot, legend, showdef factors_1(n):
step = 2 if n%2 else 1
return set(reduce(list.__add__,
([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))def factors_2(n):
return set(reduce(list.__add__,
([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))X = range(1,100000,1000)Y = []for i in X:
f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
Y.append(f_1/f_2)plot(X,Y, label='Running time with/without parity check')legend()show()X =范圍（1,100,1） 
這里沒有顯著差異，但數字越大，優勢顯而易見：
X =范圍（1,100000,1000）（僅奇數）
X =范圍（2,100000,100）（僅偶數）
X =范圍（1,100000,1001）（交替奇偶校驗）
呼喚遠方
TA貢獻1856條經驗 獲得超11個贊
agf的答案非常酷。我想看看是否可以重寫它以避免使用reduce()。這就是我想出的：
import itertools flatten_iter = itertools.chain.from_iterabledef factors(n): return set(flatten_iter((i, n//i) for i in range(1, int(n**0.5)+1) if n % i == 0))
我還嘗試了一個使用棘手的生成器函數的版本：
def factors(n): return set(x for tup in ([i, n//i] for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)
我通過計算計時：
start = 10000000end = start + 40000for n in range(start, end): factors(n)
我跑了一次讓Python編譯它，然后在time（1）命令下運行三次并保持最佳時間。
減少版本：11.58秒
itertools版本：11.49秒
棘手的版本：11.12秒
請注意，itertools版本正在構建一個元組并將其傳遞給flatten_iter（）。如果我更改代碼來構建列表，它會稍微減慢：
iterools（列表）版本：11.62秒
我相信棘手的生成器函數版本在Python中是最快的。但它并不比降低版本快得多，根據我的測量值大約快4％。
添加回答
舉報
0/150
提交
取消