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

подсказки:

• какова формула для 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 ).

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

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

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

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

 while True: 

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

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

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

• Вы должны прервать цикл, установив 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 + bb += 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 секунд, так что до минуты с этими изменениями.

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

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