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

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

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

Число треугольников – это число в последовательности суммы чисел, т.е. 1 + 2 + 3 + 4 + 5 …

Я уверен, что это рабочий код, но я не знаю, потому что мой компьютер слишком долго его вычисляет. Кто-нибудь знает, как сделать программу немного быстрее.
Благодарю.

import math def main(): l = [] one = 0 a = 1 b = 2 while one == 0: a = a + bb += 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() 

6 Solutions collect form web for “числа треугольников в 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

  • ValueError: требуется больше, чем 2 значения для распаковки в Python 2.6.6
  • Пипарация Питона: реализация грамматика для анализа логического выражения AND
  • python распаковать маленький endian
  • Получение последнего элемента данных - Google App Engine - Python
  • ошибка импорта при связывании с использованием py2exe
  • Воссоздание предложения с его позиций
  • Почему функция «len» не унаследована словарями и списками в Python
  • У PyCharm есть автозаполнение пути файла?
  • Python - лучший язык программирования в мире.