Числа треугольников в 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