числа треугольника в питоне

Question

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

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

Номер треугольника - это число в последовательности суммы чисел, то есть 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 какое-либо значение, отличное от 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 секунд, что намного меньше минуты с этими изменениями.

Answer 4

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

while True:

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

Answer 5

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

Answer 6

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

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