Проект Эйлера #12 (очень кратно треугольных) в Python 3.х


Я новичок в программировании и просто начал с Python, я пытаюсь работать через задачи проект Эйлера.

Я написал программу для решения проекта Эйлера #12, в которой просит наименьшего числа формы 1+ 2 + 3 + ... + н , которая имеет более 500 делителей. Она прекрасно работает с меньшего числа, как 100, но занимает слишком много времени, пытаясь найти до 500 факторов. Я сдался после примерно 20 минут. Я хотел бы помочь оптимизировать мой код, чтобы сделать его быстрее.

Я в принципе сделал функцию, которая находит треугольное число из заданного числа и другую функцию, которая подсчитывает количество факторов/делителей числа. Я сделал while цикл, в котором число увеличивается до треугольное число само по себе имеет более 500 факторов.

И вот мой код:

#Starts the timer to measure time taken for code to run:
import time
start_time = time.time()

#Returns the triangular number of 'num':
def triangular(num):
    return int((num*(num+1))/2)

#Returns the number of factors(divisors) of 'num':
def facCount(num):
    summ = 0
    for i in range(1, num+1):
        if num % i == 0:
            summ += 1
    return summ

#Declares x (starting value):
x = 0

#main:

while True:
    #Checks if number of factors for the triangular of x is above 500
    if facCount(triangular(x)) > 500:
        #Sets the value of 'ans' to the triangular of 'x':
        ans = triangular(x)
        #Exits the loop since answer is found
        break
    x += 1

#Prints answer (the first triangular number that has more than 500 factors):
print(ans)

#Prints the time taken for code to execute:
print("--- %s seconds ---" % (time.time() - start_time))


Комментарии
3 ответа

Ваша функция facCount, Что должно быть нечто вроде count_factorsпо словам питона официальный стиль-руководство, PEP8, можно значительно улучшить, заметив, что если num % i == 0тогда автоматически num % num / i == 0 (другими словами, факторы всегда приходят парами, за исключением, если число является квадратом, то в таком случае вам двойной счет один). Это означает, что вы должны проверить факторы до \$\функция sqrt{Н}\$:

from math import sqrt

def count_factors(num):
"""Return the number of factors of `num`"""
sum_ = 2 * sum(num % i == 0 for i in range(1, int(sqrt(num)) + 1))
if int(sqrt(num))**2 == num:
sum_ -= 1
return sum_

Я также добавил строкой документации , описывающий, что делает функция в доступной форме.

Другое улучшение касается, как вы получите треугольных. В то время как это хорошо, чтобы знать формулу Гаусса, ИМО именно здесь легче просчитать их. Ваша функция должна сделать один шаг, одно умножение и одно деление, когда все, что вам действительно нужно, это одно дополнение в каждой итерации цикла:

from itertools import count

def triangular_nums():
"""Yield the triangular numbers"""
t = 0
for i in count():
t += i
yield t

Если, по какой-то причине, вам не нравится itertoolsвы также можете заменить его с while True петли.

В Python 3+, Вы можете использовать новую функцию itertools.accumulate (3.2+) и новое ключевое слово сочетание yield from (3.3+), Как уже упоминалось в комментарии @MaartenFabré:

from itertools import accumulate, count

def triangular_nums():
yield from accumulate(count())

С этим вашим main функция (которую вы должны либо сделать реальную функцию или, по крайней мере, поставить под if __name__ == "__main__": гвардии) будет:

def main():
for t in triangular_nums():
if count_factors(t) > 500:
return t

if __name__ == "__main__":
ans = main()
if ans is not None:
print(ans)

Сроки, необходимо учесть и сделать в оформитель:

import time

def timeit(func):
def wrapper(*args, **kwargs):
start = time.time()
ret = func(*args, **kwargs)
print("--- %s seconds ---" % (time.time() - start))
return ret
return wrapper

@timeit
def main():
...

5
ответ дан 2 апреля 2018 в 07:04 Источник Поделиться

Смысл этого конкретного вопроса проект Эйлера является научить вас про кол-во-делители функции.


def triangular(num):
return int((num*(num+1))/2)

#Returns the number of factors(divisors) of 'num':
def facCount(num):
summ = 0
for i in range(1, num+1):
if num % i == 0:
summ += 1
return summ


Заметим, что некоторые из факторов triangular(n) также факторами triangular(n+1). Почему? Как вы можете пользоваться этой причине, чтобы избежать делать ту же работу более одного раза?


Оставляя в стороне алгоритмических соображений


def triangular(num):
return int((num*(num+1))/2)

не нужно int если вы используете целочисленное деление:

def triangular(num):
return num * (num + 1) // 2

2
ответ дан 3 апреля 2018 в 09:04 Источник Поделиться

Вы должны проверить От До кол-во/2, кол-во/2 является крупнейшим фактором на четное число, то корень, чтобы получить самый большой множитель. И присоединяет к себе в список.

0
ответ дан 16 декабря 2018 в 04:12 Источник Поделиться