Мой первый ответ ускорил исходный расчет от вопроса.
Вот еще один ответ, который решает его по-другому: просто найдите все основные множители каждого числа, а затем умножьте их вместе, чтобы перейти прямо к ответу. Другими словами, это автоматизирует процесс, рекомендованный poke в комментарии.
Он заканчивается за доли секунды. Я не думаю, что есть более быстрый способ сделать это.
Я выполнил поиск в Google по запросу «найти простые факторы Python» и обнаружил следующее:
http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/
С этого момента я нашел ссылку на factor.py (написанную Майком Хансеном) с некоторыми полезными функциями:
https://gist.github.com/weakish/986782#file-factor-py
Его функции делали не совсем то, что я хотел, поэтому я написал новый, но использовал его pull_prime_factors(), чтобы выполнить тяжелую работу. Результатом было find_prime_factors(), которое возвращает список кортежей: простое число и число. Например, find_prime_factors(400) возвращает [(2,4), (5,2)], потому что главные факторы 400: (2 * 2 * 2 * 2) * (5 * 5)
Затем я использую простой defaultdict(), чтобы отследить, сколько мы видели до сих пор каждого простого фактора.
Наконец, цикл умножает все вместе.
from collections import defaultdict
from factor import pull_off_factors
pf = defaultdict(int)
_primes = [2,3,5,7,11,13,17,19,23,29]
def find_prime_factors(n):
lst = []
for p in _primes:
n = pull_off_factors(n, p, lst)
return lst
def find_solution(low, high):
for num in xrange(low, high+1):
lst = find_prime_factors(num)
for n, count in lst:
pf[n] = max(pf[n], count)
print "prime factors:", pf
solution = 1
for n, count in pf.items():
solution *= n**count
return solution
if __name__ == '__main__':
solution = find_solution(1, 20)
print "answer:", solution
РЕДАКТИРОВАТЬ: Ого, я просто взглянул на @ J.F. Ответ Себастьяна на связанный вопрос. Его ответ, по сути, аналогичен приведенному выше коду, но гораздо проще и элегантнее. И это на самом деле быстрее, чем приведенный выше код.
Наименьшее общее кратное для 3 или более чисел
Я оставлю вышеупомянутое, потому что я думаю, что функции могут иметь другое использование в Project Euler. Но вот решение Дж. Ф. Себастьяна:
def gcd(a, b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""Return lowest common multiple."""
return a * b // gcd(a, b)
def lcmm(*args):
"""Return lcm of args."""
return reduce(lcm, args)
def lcm_seq(seq):
"""Return lcm of sequence."""
return reduce(lcm, seq)
solution = lcm_seq(xrange(1,21))
print "lcm_seq():", solution
Я добавил lcm_seq(), но вы также можете позвонить:
lcmm(*range(1, 21))