Euler Project problem #12 Python 代码给出了奇怪的结果

Question

我正在尝试解决 Project Euler 的 problem number 12。这是问题所在：

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?

我定义了两个函数来完成这项工作：

1) allfactor(x)：这给了我们一个列表形式的给定数字的所有因子。示例：allfactor(10) 给我们 [1, 2, 5, 10]

2)TriangularNo(x)：这给了我们第 n 个三角数。例子 TriangularNo(5) 给我们 5

这是我写的完整代码：

facs=[]

def allfacof(x):
    for i in range(1,int(x/2)+1):
        if x%i==0:
            facs.append(i)
        else:
            pass
    facs.append(x)
    return(facs)



def TriangularNo(x):
    no=0
    for i in range(1,x+1):
        no=no+i
    return(no)

a=0 # a will tell us the number of iterations

while True:
    a+=1
    N=TriangularNo(a)
    length=(len(allfacof(N)))
    if int(length)>=500:
        print(N)
        break
    else:
        pass

当我运行这段代码时，我得到 1378 作为输出，这显然是错误的，因为 len(allfacof(1378)) 结果是 8 而不是 500按照问题的要求。

注意在 while 循环中，我使用 if int(length)>=500: 所以这意味着当我的代码运行s, length 以某种方式获得值 = 500 但是当我运行单独的函数它说它的长度是 8。

我只是找不到错误。请帮助我

Answer 1

问题是您将 facs 用作全局变量并且您只是附加到项目。您应该使它成为 allfacof() 的成员，以便它在每个值后清除。如果你查看 facs 然后你会发现它等于

1, 1, 3, 1, 2, 3, 6, 1, 2, 5, 10 ...

Answer 2

虽然将 facs 移动到 all_factors_of() 可以解决您眼前的问题，但此代码的下一个问题是性能。让我们首先考虑三角形数的生成。 @Voo建议的优化：

def TriangularNo(n):
    return n * (n + 1) / 2

如果我们正在寻找任意三角形数字，

很好——但我们不是。我们正在寻找连续三角形数字，因此在这种情况下，公式减慢我们的代码！按顺序进行时，您只需进行几次加法即可获得下一个三角形编号——但使用公式时，您需要进行加法、乘法和除法！如果你按顺序去更贵。由于我们是按顺序进行，这似乎是对 Python 生成器的完美使用：

def triangular_number_generator():
    triangle = number = 1

    while True:
        yield triangle
        number += 1
        triangle += number

这清楚地表明了获得下一个三角形编号所需的两个加法。现在让我们考虑一下您的因式分解函数：

您的因式分解函数在按顺序生成因数时会降低性能。但我们只关心 个因素 ，顺序无关紧要。所以当我们分解 28 时，我们可以同时将 1 和 28 添加到因子列表。同上 2 和 14——使 14 成为我们的新上限。类似地 4 和 7，其中 7 成为新的上限。所以我们更快地收集因子并快速降低我们需要检查的上限。这是代码的其余部分：

def factors_of(number):
    divisor = 1
    limit = number
    factors = []

    while divisor <= limit:

        if number % divisor == 0:
            factors.append(divisor)

            remainder = number // divisor

            if remainder != divisor:
                factors.append(remainder)

            limit = remainder - 1

        divisor += 1

    return factors

triangular = triangular_number_generator()
number = next(triangular)
factors = factors_of(number)

while len(factors) <= 200:
    number = next(triangular)
    factors = factors_of(number)

print(number)

比较如何？如果我们运行您的固定代码的下限 > 200 个因子，则需要大约分钟才能得出答案 (2031120)。上面的代码大约需要秒的 1/3。现在考虑达到 > 500 个因素需要多长时间。最后，实现既定目标：

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

你的原始代码中的这个比较：

if int(length)>=500:

需要改为：

if length > 500:

尽管因子计数的跳跃方式对 500 没有影响。但是对于较小的限制，对于测试，它会产生影响。

Euler Project problem #12 Python 代码给出了奇怪的结果

Euler Project problem #12 Python code gives weird results

python

number-theory