python中的三角形数字

Question

我正在努力解决这个问题:

拥有超过500个除数的第一个三角形数的值是多少？

三角形数字是数字总和序列中的数字,即1 + 2 + 3 + 4 + 5 ......

我很确定这是有效的代码,但我不知道,因为我的计算机计算时间太长.有没有人知道如何使程序更快一点.
谢谢.

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        for x in range(1, int(a/2 + 1)):
            if a % x == 0:
                l.append(x)
                if len(l) > 499:
                    print a 

if __name__ == '__main__':
    main()

Answer 1

提示:

• n第三角数的公式是什么？
• n和n+1没有共同的因素(除1).问题:给出的因素数量n以及n+1如何计算因子的数量n*(n+1)？怎么样n/2和(n+1)(或n和(n+1)/2)？
• 如果你知道n如何计算除数的所有主要因素n？

如果您不想更改算法,那么您可以通过以下方式加快算法速度:

• 替换l.append为factor_count += 1
• 枚举int(a**.5)而不是a/2(factor_count += 2在这种情况下使用).

Answer 2

你必须多考虑并使用较少的蛮力来解决Project Euler问题.

在这种情况下,您应该调查三角形数具有哪个和有多少除数.从头开始,寻找模式,尝试了解问题.

Answer 3

你没有更新它的值one,所以你的程序永远不会结束.

Answer 4

为了理智,你应该使用

while True:

并摆脱one.

Answer 5

首先,人们告诉你,你不能在一分钟内用蛮力解决这个问题是错误的.针对此大小问题的强力算法将在几秒钟内运行.

其次,您发布的代码有几个问题,其中一些已经提到过.

• 您应该通过设置one除了0达到目标条件(当前的目标)之外的某个值来终止循环print a.
• 你永远不会重新初始化列表(l = []).这应该是每次重新计算的时间内完成a,并b,您输入的循环权利之前.
• 问题要求第一个三角形数字有超过 500个除数.你的终止条件应该是if len(l) > 500:.
• 你可能不想print a在for循环中,但要等到while循环完成.

真正让你失望的是,对于每个三角形数字,a你要检查每个值a / 2,看看它是否为除数.您只需要检查最大平方根的值a.这种方式的每个值x,如果x是一个除数你可以添加x和a / x到列表中.

这是您的代码,其中包含我在上面概述的修改:

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        l = []

        sqrt_a = int(math.sqrt(a))

        for x in range(1, sqrt_a + 1):
            if a % x == 0:
                l.append(x)
                if x < math.sqrt(a):
                    l.append(a // x)
                if len(l) > 500:
                    # print(a)
                    one = 1

    print(a, b, len(l))

if __name__ == '__main__':
    main()

您将看到它在大约5或6秒内运行,因此在一分钟内完成这些修改.