我寫了下面的功能，找到一個給定的自然數的所有約數，並返回它們作爲一個列表進行了一些優化的所有除數：尋找
def FindAllDivisors(x):
divList = []
y = 1
while y <= math.sqrt(x):
if x % y == 0:
divList.append(y)
divList.append(int(x/y))
y += 1
return divList
它的作品真的很好，不同的是它真的很慢當輸入是一個18位數字時。你對我如何加快速度有什麼建議嗎？
更新：
我有以下方法基於費馬小定理來檢查素性：
def CheckIfProbablyPrime(x):
return (2 << x - 2) % x == 1
檢查單號時，此方法是非常有效的，但是我不確定我是否應該用它來編譯所有素數達到某個邊界。
您可以通過計算素因子分解找到數字的所有除數。每個除數必須是因式分解中的素數的組合。
如果你有質數的列表，這是一種簡單的方式來獲得分解：
def factorize(n, primes):
factors = []
for p in primes:
if p*p > n: break
i = 0
while n % p == 0:
n //= p
i+=1
if i > 0:
factors.append((p, i));
if n > 1: factors.append((n, 1))
return factors
這就是所謂的審判庭。有很多更有效的方法來做到這一點。有關概覽，請參閱here。
計算除數是現在很容易：
def divisors(factors):
div = [1]
for (p, r) in factors:
div = [d * p**e for d in div for e in range(r + 1)]
return div
計算所有除數的效率取決於算法來尋找素數（小概述here），並在分解算法。後者總是很慢，非常大的數字，你可以做的事情不多。
我的第一個想法也是關於素數的因子，但我不確定他們的搜索是否更快，而不是直接將N除以所有數字 - 我們仍然會篩選直到sqrt（N），然後花O（ 1）對於每個素數的組合（我們仍然需要穿過它）。 –
我對我的問題添加了一個小修改。所以如果我使用我的當前素數測試，這是否足夠有效，還是應該改變我的測試？ –
@Bob，主要列表可以預先計算，即使需要檢查多個數字，也只能進行一次。分解的優點是隻檢查素數。對於一個數字你是對的，它並不重要。 –
我建議將結果math.sqrt(x)存儲在一個單獨的變量，然後檢查y反對它。否則，將在每個步驟while和math.sqrt重新計算絕對不是輕量級操作。
也可以嘗試將結果附加到字符串而不是列表。 –
這是代碼優化，很好，但你會有相同的「大O」。 Ben Ruijl解決方案確實可以減少算法的複雜性，從而節省大數量的時間。 – MatthieuW
我會做素因子分解，然後從該結果計算所有除數。
我不知道是否有很多的性能命中，但我非常確定，轉換爲int是不必要的。至少在Python 2.7中，int x/int y返回一個int。
在Python 3中，它沒有。在那裏你可以使用'//'來進行地板劃分。 –
您是否使用'CheckIfPrime'來查看是否可以跳過某個x的分區？你應該小心這一點，因爲你可以得到誤報：'CheckIfPrime'過濾大部分數字，但一些複合仍然會產生'真'！ –
@BenRuijl請給我一個例子，非常感謝！ –
由於[Fermat pseudoprimes]（http://en.wikipedia.org/wiki/Fermat_pseudoprime），您的'CheckIfPrime'函數不起作用。例如，'CheckIfPrime（341）'爲True，但是341 = 11 * 31。如果'CheckIfPrime'爲False，那麼這個數字肯定是複合的，但是反過來並不成立。 [對不起，我錯過了BenRuijl先前的評論。不過，如果僅將它用作「CheckIfProbablyPrime」，它仍可能有用。 – DSM