Что не так с моим Python-решением для Project Euler # 12?

Question

Возможное предупреждение о спойлере

Я потратил целую вечность, пытаясь улучшить этот алгоритм и выяснить, что происходит, но я не могу понять, почему выводимый ответ неверен.

Я пытаюсь решить Project Euler # 12 , чтобы получить наименьшее треугольное число, имеющее более 500 делителей, но он говорит, что мой ответ неверен.

Вот мой код Python:

import time

# function to get the number of divisors
def div(n):
    d=2
    for i in range(2,int(n**.5)+2):
        if (n % i) == 0:
            d += 1
    return d

start = time.time()

w = True
n=m=1
while w:
    n += 1
    s = (n*(n+1))/2 # nth triangle number
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"divisors"
        if r > 500:
            w = False

print "Solved in",((time.time()-start)*1000),"milliseconds"

И вывод для этого кода такой (через 66 секунд):

3 has 2 divisors
6 has 4 divisors
36 has 6 divisors
120 has 9 divisors

...

76576500 has 289 divisors
103672800 has 325 divisors
236215980 has 385 divisors
842161320 has 513 divisors
Solved in 65505.5799484 milliseconds

Однако, если я ввожу 842161320 в задачу Project Euler, он говорит, что это неправильно.

Что я делаю не так?

Answer 1

Я вижу две ошибки:

• Ваша функция div не работает: div(24) == 5, тогда как она должна быть 8
• Ваше 1-е треугольное число будет 3, хотя оно должно быть 1

Вы можете реализовать работающий div так:

import math
def divisors(n):
  return sum(1 for x in range(1, n+1) if n % x == 0)

Кроме того, этот код чертовски неэффективен, некоторые предложения по его улучшению:

Вместо расчета n-го треугольного числа по формуле используйте скользящую сумму:

import itertools

s = 0
for i in itertools.count(1):
  s += i
  if div(s) > 500:
    print s
    break

Кроме того, используйте простые коэффициенты для вычисления количества делителей . Вы можете создать кеш с основным фактором для максимальной производительности.

Answer 2

Вы недооцениваете общее количество делителей. 36, например, имеет 9 делителей: 1,2,3,4,6,9,12,18,36. Это правда, что алгоритму нужно только проверять числа, меньшие sqrt(n), чтобы найти все делители, но вам все равно нужно включить в ваш счет подразумеваемые «большие» делители.

Answer 3

Решено

С помощью Niklas и меняя мой метод div, я получил ответ.Кроме того, теперь это занимает всего 8% времени, которое занимал мой предыдущий алгоритм.

Алгоритм теперь выглядит следующим образом:

import time
import itertools

def div(n):
    d=0
    for i in range(1,int(n**.5)+1):
        if (n % i) == 0:
            d += 1
    return 2*d

start = time.time()

s = m = 0
for i in itertools.count(1):
    s += i
    r = div(s)
    if r > m:
        m = r
        print s,"has",r,"factors"
        if div(s) > 500:
            break

print "Solved in",((time.time()-start)*1000),"milliseconds"