Euler＃12，我的Python程序出了什麼問題？

Question

第十二問題是：通過將自然數生成

三角形號的序列。因此，第7個三角形數將是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.前十項將是：

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

讓我們列出前七個三角數的因素：

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是第一個具有 的三角形數字五個因子。

第一個三角形數字的值超過五個 個百分比是多少？

---

我在Python 3.4

def Nfactor(n): 
    k=2 
    c=0 
    while k<=n: 
     if n%k==0: 
      n=n//k 
      c+=1 
     else: 
      k=k+1  
    return c 

a=1  
for i in range(10**6): 
    a+=i 
    if Nfactor(a)>=500: 
     print(a) 
     break 

---

節目，我等了10多分鐘，永遠不會有答案。對於我自己而言，我的程序並不算太壞，必須在幾秒鐘內運行......好吧，這讓我瘋狂大聲笑，我沒有發現我的錯誤。

你能幫助我嗎？

預先感謝您！

---

編輯

我現在的解決辦法：

import math 

def Nfactor(n): 
    if n==1: 
     return 1 
    else: 
     c=0 

     for i in range(1, int(math.sqrt(n)+1)): 
      if n%i==0: 
       c+=1 
     return c*2 

a=0  
for i in range(1,10**6): 
    a+=i 
    if Nfactor(a)>=500: 
     print(a) 
     break 

Answer 1

您將最有可能得不到任何輸出。

的a你的最後一個值是499999500001，而對於這NFactor(..)是500的最小數量爲2^500是3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376

---

一些提示（我有它運行在不到一個工作示例第二現在，但我想這張貼在這裏將是一個擾流板）：

• 作爲另一個（刪除eted）的答案指出，考慮到一個數的素因子數，一個數的除數的數量是（每個素因子的數加1）的乘積，即如果一個質子因子p出現N次，則可以構建N+1產品從0到p^N，並結合素數的不同權力。

• 爲@NightShadeQueen指出，一旦你計算的數字n的因式分解，將其存放在緩存中（我用的是dict映射從n到dict本身從一個素數映射到的數它發生的時間）。當要求計算給定數字的素因子集時，首先檢查緩存，然後從2開始掃描以查看是否可以找到第一個因子。然後用n第一因素等

• 尋找n個素因子分爲遞歸調用函數，沒有必要去到N，你可以找到素因子當sqrt(n)

• 停止（k在你的函數Nfactor(..)），你可以檢查k=2，k=3（即如果2分n，如果3個分歧n等），然後在第2步遞增k（僅k=2後進行測試的k奇數值）

在上面的評論中提到

• ，開始a=1和使用range(1,10**6)而不是爲i

在我的解決方案未使用;用我最喜愛的搜索引擎發現：

• 的i'th三角形數量是a = i * (i+1)/2，所以你可以結合i和i+1的主要因素（去除2出現一次）。由於 i和i+1不會共享任何常見的素因子，因此您可以從i和i+1的因子數量中推導出a的因子數量。

Answer 2

一些想法...

1. 如果我正確地讀，你每天有效測試數n在2至到n。你應該只能測試sqrt（n）。 （更新：道歉，我沒有想清楚...它需要是n/2，而不是sqrt（n）。對素數的測試只需要sqrt（n）。）
2. 運行2 ** 500 in一個python shell。我想你會發現你的測試幾乎不夠高。 :-)
3. 也許會降低......用少量因素測試您的方法？

Answer 3

您正在列出質數，但不列出其產品。在定義，28，你有7天，14和28，其中在功能您只需數數7

所以Nfactor，做它作爲問，應該是這樣的：

def Nfactor(n): 
    k=2 
    c=2 
    while k<n: 
     if n%k == 0: 
      c+=1 
     k=k+1  
    return c 

但有一個非常快的方式來獲得的因素（感謝this page）：

from math import sqrt 
def Nfactor(n): 
    factors = set() 
    for x in range(1, int(sqrt(n)) + 1): 
     if n % x == 0: 
      factors.add(x) 
      factors.add(n//x) 
    return len(factors) 

而且，你不按照指示操​​作。您不會將搜索範圍限制爲由後續術語總和（1，1 + 2，1 + 2 + 3，1 + 2 + 3 + 4等）定義的數字，但會針對每個數字進行測試for i in range(10**6):）。

對有這些數字，你可以使用一個generator（見here）是這樣的：

def gen(): 
    counter = 1 
    total = 0 
    while True: 
     total += counter 
     yield total 
     counter += 1 

，然後，你可以這樣做，以找到您想要的號碼：

g = gen() 
for n in g: 
    if Nfactor(n) > 500: 
     print(n) 
     break 

Answer 4

import math 
num=2 
i=3 
def is_notprime(num): 
    j=3 
    flag=int(math.sqrt(num)) 
    while((j<=flag and num>=3)):  
     if num%j==0:  
     return True 
     break 
     else: 
     j=j+2 
def check_div(num): 
    temp=1 
    a=i 
    if(num%2==0 and num>1): 
    while(num%2==0): 
     num=num/2 
     temp+=1 
    for j in range(3,int((num+5)/2),2): 
    count=1 
    if((is_notprime(num) and num>1) or num==j): 
     while num%j==0: 
     num=num/j 
     count+=1 
    elif num>1: 
     temp=temp*2 
     break 

    temp=temp*count 
    print("divisor is and %d ans is %d" %(temp,a)) 
    return(temp) 
while(i>=1): 
    if(check_div(i)>5): 
    break 
    num+=1 
    i=num*(num+1)/2