Как сократить время выполнения упражнений Project Euler

Question

У меня возникли проблемы со временем работы с Project Euler. Это упражнение можно найти здесь: Упражнение Project Euler 12 . Мое решение:

def triangularnr(n):
    T_n = n*(n+1)/2     #Function to calculate triangular numbers 
    return T_n

for n in range(1,1*10**8):  #Nr with over 500 divisors is large, large range required
    count = 2   #Every nr is divisible by itself and by 1, thus initially count = 2 
    for i in range(2,int(triangularnr(n))): #Defining i to find divisors 
        if triangularnr(n)%i == 0:
            count+=1 #Incrementing count to count the nr of divisors 
    if count > 500: #If a triangularnr has over 500 divisors we want to print the nr
        print(triangularnr(n))
        break

Я попытался оптимизировать код, уменьшив количество необходимых шагов и используя математическую формулу для чисел tri angular. Мой код работает для 5 делителей, но на поиск 500 делителей уходит много времени. Вчера я позволил коду работать в течение 3 часов, но ничего не выводит. Должен ли я позволить коду работать более 3 часов, или вывод никогда не будет напечатан, поскольку с моим кодом что-то не так?

Answer 1

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

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

Более эффективным способом было бы рассмотреть разложение на простые числа вашего тестового числа. Любое целое число можно записать как произведение простых чисел. Предположим, что N имеет простые множители p1, p2, ..., pn с показателями k1, k2, ..., kn, т.е. N == p1**k1 * p2**k2 * ... * pn**kn, тогда количество делителей N равно (k1+1)*(k2+1)*...*(kn+1). Таким образом, нахождение числа делителей эквивалентно нахождению простых множителей числа, что значительно ограничивает количество целых чисел, которые необходимо проверить.

Еще одна вещь, которую следует понять, это то, что если целые числа N1 и N2 не имеют общих простых множителей (что имеет место для N и N+1), количество делителей N1*N2 равно количеству делителей N1, умноженному на количество делителей N2. Это означает, что, поскольку вы рассматриваете числа в форме N*(N+1)//2 и поскольку N и N+1 не имеют общих простых множителей, количество делителей ваших трех angular чисел равно произведению количества делители N//2 и количество делителей N+1 для четных N, а также произведения количества делителей N и количества делителей (N+1)//2 для нечетных N.

Answer 2

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

Ваш алгоритм неэффективен, потому что:

• Tri angular числа увеличиваются на квадрат (развернуть n * (n + 1) / 2)
• Ваш алгоритм перебирает каждое три angular число

Эти две вещи означают, что ваш алгоритм, вероятно, имеет сложность из n ^ 3. Например. удвоение необходимого количества факторов увеличивает пространство поиска в 8 раз.

Один совет, который может оказаться полезным, заключается в том, что если у вас есть два числа, a и b, количество факторов a * b равно к количеству факторов a, умноженному на количество факторов b. Например, 5 имеет два фактора (5, 1), а 14 имеет 4 фактора (1, 2, 7 и 14). Из этого мы знаем, что 5 * 14 имеет 2 * 4 множителя, без необходимости искать числа от 1 до 70.

К счастью для вас, три angular числовая формула T_n = n * (n + 1) / 2 уже разбита на две части. факторов, поэтому вам нужно что-то закодировать, чтобы:

• Определить, является ли n или n + 1 четным
• Разделить четный коэффициент на 2
• Вычислить количество множителей этих множителей
• Умножьте эти числа, чтобы найти число множителей три angular число

Надеюсь, что это помогло :)