Euler#12，我的 Python 程序出了什么问题？

Question

第十二题是：

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

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 We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

我的程序在Python3.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

您很可能得不到任何输出。

Your last value of a is 499999500001 while the smallest number for which NFactor(..) is 500, is 2^500 which is 3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376

一些提示（我有一个工作示例，现在运行不到一秒，但我想将其发布在这里会剧透）：

正如另一个（已删除的）答案所指出的，给定一个数的素数个数，一个数的除数数是（每个素数加一的数）的乘积，即如果素数 p 出现 N 次，您可以从 0 到 p^N 构建 N+1 乘积，并结合素数的不同幂。
正如@NightShadeQueen 指出的那样，一旦计算出数字 n 的质因数分解，请将其保存在缓存中（我使用来自 n 到 dict 本身从素数映射到它出现的次数）。当被要求计算给定数字的质因数集合时，首先检查缓存，然后从 2 开始向上扫描，看看是否可以找到第一个因数。然后用 n 除以第一个因子等递归调用函数
求n的质因数，不用上到n，可以停在sqrt(n)
当找到质因数时（k 在你的函数 Nfactor(..) 中），你可以检查 k=2，k=3（即如果 2 除 n, if 3 除以 n 等）然后递增 k 步长为 2（仅测试 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

一些想法...

如果我没看错的话，您实际上是在测试从 2 到 n 的每个数字 n。您应该能够测试到 sqrt(n)。（更新：抱歉，我没有想清楚......它需要 n/2，而不是 sqrt(n)。测试素数只需要 sqrt(n)。）
运行 2 ** 500 在 python shell。我想你会发现你的测试还不够高。 :-)
也许降低...用更少的因素测试你的方法？

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

Euler#12，我的 Python 程序出了什么问题？

Euler#12, what's wrong with my Python program?

python

python-3.4