Оптимизируйте решение Project Euler 12 (Python)

Question

У меня есть следующий код для Project Euler Problem 12. Однако для выполнения требуется очень много времени. У кого-нибудь есть предложения по его ускорению?

n = input("Enter number: ") 
def genfact(n): 
    t = [] 
    for i in xrange(1, n+1): 
     if n%i == 0: 
      t.append(i) 
    return t 

print "Numbers of divisors: ", len(genfact(n)) 
print 

m = input("Enter the number of triangle numbers to check: ") 
print 
for i in xrange (2, m+2): 
    a = sum(xrange(i)) 
    b = len(genfact(a)) 
    if b > 500: 
     print a 

Для п, я ввести произвольное число, например, 6 раз, чтобы проверить, действительно ли она возвращает длину списка ряда факторов. Для м, введите ввод 80 000 000

Он работает относительно быстро для небольших номеров. Если я введу b > 50; он возвращает 28 для a, что является правильным.

Answer 1

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

Попадая факторы п: Как @usethedeathstar упоминалось, можно проверить факторы только до n/2. Тем не менее, мы можем сделать лучше, проверяя только до квадратного корня из п:

let n = 36 
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1) 

Как вы можете видеть, что петли вокруг после 6 (квадратного корня из 36). Нам также не нужно явно возвращать факторы, просто узнайте, сколько есть ...так что просто рассчитывать их с генератором внутри суммы():

import math 

def get_factors(n): 
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i) 

Testing треугольные числа

я использовал функцию генератора, чтобы получить треугольные номера:

def generate_triangles(limit): 
    l = 1 
    while l <= limit: 
     yield sum(range(l + 1)) 
     l += 1 

И, наконец, начать тестирование:

def test_triangles(): 
    triangles = generate_triangles(100000) 
    for i in triangles: 
     if get_factors(i) > 499: 
      return i 

Запуск этого с профилировщика, он завершает менее чем за 10 секунд:

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds 

Самая большая экономия здесь время get_factors(n) тестирование только до квадратного корня из п - это делает его heeeaps быстрее и сэкономить кучу памяти накладные расходы, не генерируя список факторов.

Как я уже сказал, все еще не очень - я уверен, что есть более элегантные решения. Но это соответствует быстрому счету :)

Answer 2

один из подсказок я могу дать

def genfact(n): 
    t = [] 
    for i in xrange(1, n+1): 
     if n%i == 0: 
      t.append(i) 
    return t 

изменение, чтобы

def genfact(n): 
    t=[] 
    for i in xrange(1,numpy.sqrt(n)+1): 
     if(n%i==0): 
      t.append(i) 
      t.apend(n/i) 

, так как, если есть делитель, чем так Ь = п/а, так как A * B = а * n/b = n, Это должно помочь части уже (не уверен, что в вашем случае квадрат возможен, но если это так, добавьте еще один случай, чтобы исключить добавление одного и того же номера дважды)

Вы могли бы разработать рекурсивную вещь тоже (например, если это что-то вроде 2 8, вы получаете 1,28,2,14, и в тот момент, когда вы знаете 14, вы добавляете что-то, чтобы действительно помнить делителей 14 (memoize), чем проверить, являются ли они alraedy в списке, а если нет, добавьте их в список вместе с 28/d для каждого из делителей 14, а в конце просто вытащите дубликаты

Если вы считаете, что мой первый ответ все еще не достаточно быстрый, попросите больше, и я проверит, как это будет сделано, чтобы быстрее решить эту проблему с помощью еще нескольких трюков (возможно, возможно использовать сито erastothenes или так же, и некоторые другие трюки можно было бы придумать, если вы захотите действительно взорвать проблему до огромных размеров , как проверить первый с более чем 10k делителей или около того)

Answer 3

while True: 
    c=0 
    n=1 
    m=1 
    for i in range(1,n+1): 
     if n%i==0: 
      c=c+1 
      m=m+1  
      n=m*(m+1)/2 
      if c>500: 
       break 
print n