優化幫助找到最大因數

Question

我想解決歐拉項目的問題12。第一個三角形數字的值超過500個因數是多少？ （第7個三角形數將是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28）。這是我的代碼，但速度不夠快。 你有沒有優化技巧？

n=0 
a=0 
list=[] 
maxcount=0 


while True: 
    n+=1 
    a+=n 
    count=0 
    for x in range(1,int(a+1)): 
     if a%x==0: 
      count+=1 
      if count>maxcount: 
       maxcount=count 
       print a, "has", maxcount, "dividors" 

謝謝！

Answer 1

從減少搜索空間開始，不需要查看不是三角形數字的數字。也可以試着看看除數range(1, sqrt(n))而不是range(1, n)

Answer 2

除了數論：嘗試緩存，並以相反的方式做事。例如：當你已經知道300有18個除數（以及它們是什麼）時，對於一個可被300除的數字，這意味着什麼？你能緩存這些信息嗎？ （當然可以。）

純python加速hack不會幫助你，你需要一個更好的算法。

Answer 3

抓住從這個問題上的代碼，實現了非常快的因式分解：
Fast prime factorization module

然後用這個問題的答案，以您的首要因素轉換成所有除數的列表（長度是你想要什麼） ：
What is the best way to get all the divisors of a number?

例如，可以添加以下功能（改編自第二鏈路）到模塊的從第一連桿的底部：

def alldivisors(n): 
    factors = list(factorization(n).items()) 
    nfactors = len(factors) 
    f = [0] * nfactors 
    while True: 
     yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1) 
     i = 0 
     while True: 
      if i >= nfactors: 
       return 
      f[i] += 1 
      if f[i] <= factors[i][1]: 
       break 
      f[i] = 0 
      i += 1 

然後在您的代碼中計算除數，您將使用len(list(alldivisors(a)))，這將比您當前使用的蠻力方法快得多地計算除數的數量。