Числа треугольников в python

Я пытаюсь решить проблему:

Каково значение первого числа треугольников, которое содержит более пятисот делителей?

Число треугольников - это число в последовательности суммы чисел i. 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()

Ответ 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 в этом случае).

Ответ 2

Вам нужно будет больше думать и использовать меньше грубой силы для решения вопросов Project Euler.

В этом случае вы должны исследовать, какое и сколько чисел треугольников делителей. Начните с начала, найдите шаблоны, попытайтесь понять проблему.

Ответ 3

Вы не обновляете значение one, поэтому ваша программа никогда не закончится.

Ответ 4

Просто ради сани, вы должны использовать

while True:

и избавиться от one.

Ответ 5

Прежде всего, люди, говорящие вам, что вы не можете решить эту проблему с грубой силой менее чем за минуту, ошибочны. Алгоритм грубой силы для проблемы такого размера будет работать через несколько секунд.

Во-вторых, код, который вы опубликовали, имеет несколько проблем, некоторые из них уже упомянуты.

Вы должны закончить цикл, установив one на некоторое значение, отличное от 0, как только вы достигнете своего целевого состояния (где вы в настоящее время print a).
Вы никогда не обновляете список (l = []). Это нужно делать каждый раз, когда вы пересчитываете a и b, прямо перед тем, как вводить цикл for.
Вопрос требует, чтобы первый номер треугольника имел над пятьсот делителей. Ваше условие для завершения должно быть 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 секунд, поэтому с точностью до минуты с этими изменениями.

Ответ 6

Ваш текущий алгоритм грубой силы слишком неэффективен для решения этой проблемы в листе Project Euler в течение 1 минуты. Вместо этого я предлагаю посмотреть функцию Divisor:

http://www.artofproblemsolving.com/Wiki/index.php/Divisor_function