尋找超過500個除數

我試圖解決一個問題找到超過500個除數第一三角數三角數Python程序，但有溢出錯誤尋找超過500個除數

請給一個更好的辦法

問題是

三角形數字的序列是通過添加自然數生成的。因此，第7個三角形數將是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。前十項將是：

1,3,6,10,15,21,28,36， 45，55，66 ...

讓我們列出前七個三角數的因素： 1:1 3：1,3 6：1,2,3,6- 10：1,2- ，5,10 15：1,3,5,15 21：1,3,7,21 28：1,2,4,7,14,28 我們可以看到28是第一個三角形數有超過五個因子。第一個三角形數值超過五百個除數是多少？

我的計劃是

` 
def isPrime(a): 
    m=0 
    for j in range(1,a/2+1): 
     if (a%j)==0: 
      m+=1 
    return m+1 
i=1 
n=1 
div=500 
while (i>=1): 
    l=isPrime(i) 
    ans=i 
    if l>div: 
     print ans 
     break 
    n+=1 
    i=n*(n+1)/2 
`

來源

2015-07-10 jainaman224

哪裏溢出錯誤？你有什麼想法，爲什麼溢出錯誤發生？ – bcdan

根據我這是由於無限循環 – jainaman224

溢出錯誤是由函數調用遞歸引起的，或變量超過可用內存。我不明白這個腳本會怎麼樣。另外，請包含完整的錯誤消息。 – bcdan

這個問題的關鍵是如何使你的程序更有效，你必須寫一些東西，計算更有效的方式整數除數的數量。有很多關於如何在這個論壇上做到這一點的討論，像這樣：What is the best way to get all the divisors of a number? 但是，我仍然認爲你的程序有一些問題，所以我寫了一個（仍然使用你的方法找到除數）：

def numberOfDivisors(a): 
    m=0 
    for j in range(1,a/2+1): 
     if (a%j)==0: 
      m+=1 
    return m+1 

def findNumber(): 
    n = 1 
    i = 1 
    div = numberOfDivisors(n) 
    while div < 500: 
     i += 1   
     n = i*(i+1)/2 
     div = numberOfDivisors(n) 
     print 'n = ', n 
    return n

不必要的打印只是爲了更容易地遵循代碼的工作方式。正如我所說，仍然使用非常差的方法找到除數。提高效率是解決問題的方法。這個程序不能按你的要求工作，因爲它達到6位或7位數字時速度太慢。

來源

2015-07-10 18:09:31

可以給你更好的方式，因爲它無法找到ans – jainaman224

你可以嘗試下面的解決方案：http://codereview.stackexchange.com/questions/83579/project-euler-problem-12-in-python –

找到除數的一種簡單但更有效的方法是使用數的素因式分解生成除數。找到質數因子分解是有據可查的，但我會建議使用「Eratosthenes篩」或類似的東西（link to wiki）

一旦你有素因子分解，你只需要找到存在的排列數0描述here所述的因子分解中每個素數的冪。沒有必要實際找到所有的因素:)

這就是我如何找到解決這個相同的問題，我的程序能夠在短短9秒內測試第一個12,375三角形數字。

編輯：我要指出，你可能需要考慮遞歸函數，如果你想追求這種方法，因爲你需要它來找到所有的權力在因式分解中發現的排列

來源

2016-10-27 19:22:15 mscottchristensen

尋找超過500個除數

回答

相關問題