Project Euler 5 в Python – Как я могу оптимизировать свое решение?

Недавно я работал над проблемами Project Euler в Python. Я довольно новичок в Python и по-прежнему новичок как программист.

В любом случае, я столкнулся с проблемой, связанной с скоростью, для кодирования решения проблемы №5. Проблема в,

«2520 – наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка. Какое наименьшее положительное число равномерно делится на все числа от 1 до 20?»

Я проверил вокруг, и я не смог найти что-либо по этой проблеме, относящейся к Python. Были некоторые завершенные сценарии, но я хочу, чтобы по возможности не смотреть на код другого, вместо этого желая улучшить свое.

Код, который я написал, успешно работает для примера 2520 и диапазона от 1 до 10 и должен быть непосредственно модифицирован для работы с вопросом. Однако, после запуска, я не получаю ответа. Предположительно, это очень большое число, и код не достаточно быстрый. Печать текущего проверяемого номера, похоже, поддерживает это, достигнув нескольких миллионов, не получив ответа.

Код, в его текущей реализации, выглядит следующим образом:

rangemax = 20 def div_check(n): for i in xrange(11,rangemax+1): if n % i == 0: continue else: return False return True if __name__ == '__main__': num = 2 while not div_check(num): print num num += 2 print num 

Я уже сделал пару изменений, которые, я думаю, должны помочь скорости. Во-первых, для того, чтобы число делилось на все числа от 1 до 20, оно должно быть четным, так как только четные числа делятся на 2. Следовательно, я могу увеличивать на 2 вместо 1. Кроме того, хотя я и не думал о он сам, я обнаружил, что кто-то указывает, что число, делящееся на 11-20, делится на 1 до 10. (Не проверял его, но он кажется разумным)

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

Заранее благодарим любого, кто может помочь.

16 Solutions collect form web for “Project Euler 5 в Python – Как я могу оптимизировать свое решение?”

Принимая совет Майкла Миора и тыкать, я написал решение. Я попытался использовать несколько трюков, чтобы сделать это быстро.

Поскольку нам нужен относительно короткий список проверенных номеров, мы можем предварительно построить список чисел, а не многократно называть xrange() или range() .

Кроме того, хотя было бы просто поместить числа [1, 2, 3, ..., 20] в список, мы можем немного подумать и вывести цифры:

Просто возьмите 1 выход. Каждое целое число равномерно делится на 1.

Если оставить 20 в, нет необходимости оставлять 2 дюйма. Любое целое число, равномерно делимое на 20, равномерно делится на 2 (но обратное может быть неверным). Таким образом, мы оставляем 20 и вынимаем 2, 4 и 5. Оставляем 19, так как это просто. Оставьте 18, но теперь мы можем вынуть 3 и 6. Если вы повторите этот процесс, вы получите гораздо более короткий список чисел, чтобы попробовать.

Мы начинаем с 20 и число шагов на 20, как предложил Майкл Миор. Мы используем выражение-генератор внутри all() , как предполагалось.

Вместо цикла while я использовал цикл for с xrange() ; Я думаю, что это немного быстрее.

Результат:

 check_list = [11, 13, 14, 16, 17, 18, 19, 20] def find_solution(step): for num in xrange(step, 999999999, step): if all(num % n == 0 for n in check_list): return num return None if __name__ == '__main__': solution = find_solution(20) if solution is None: print "No answer found" else: print "found an answer:", solution 

На моем компьютере это находит ответ менее чем за девять секунд.

EDIT: И если мы возьмем совет у Дэвида Заславского, мы поймем, что мы можем начать цикл на 2520 и шаг к 2520 году. Если я это сделаю, то на моем компьютере я получу правильный ответ примерно через десятую часть секунды.

Я сделал find_solution() принять аргумент. Попробуйте вызвать find_solution(2520) .

Мой первый ответ ускорил исходный расчет из вопроса.

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

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

Я выполнил поиск Google на «найти основные факторы Python» и нашел следующее:

http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/

Из этого я нашел ссылку на factor.py (написанный Майком Хансеном) с некоторыми полезными функциями:

http://sage.math.washington.edu/home/mhansen/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 

EDIT: О, ничего себе, я просто взглянул на ответ @JF Себастьяна на соответствующий вопрос. Его ответ по существу совпадает с приведенным выше кодом, но гораздо более просто и элегантно. И это на самом деле быстрее, чем приведенный выше код.

Наименьшее общее число для 3 или более номеров

Я оставлю все выше, потому что, я думаю, функции могут иметь другие применения в Project Euler. Но вот решение JF Sebastian:

 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)) 

Поскольку ваш ответ должен быть делимым на 20, вы можете начинать с 20 и увеличивать на 20 вместо двух. В общем, вы можете начать с rangemax и увеличивать на rangemax . Это уменьшает количество раз, когда div_check вызывается на порядок.

Перечисление списков происходит быстрее, чем для циклов.

Сделайте что-нибудь подобное, чтобы проверить номер:

 def get_divs(n): divs = [x for x in range(1,20) if n % x == 0] return divs 

Затем вы можете проверить длину массива divs, чтобы увидеть, присутствуют ли все числа.

Здесь были размещены два разных типа решений. Один тип использует вычисления gcd ; другой использует основную факторизацию. Я предлагаю третий тип, основанный на принципе простой факторизации, но, вероятно, будет намного быстрее, чем сама факторизация. Он опирается на несколько простых наблюдений о простых степенях – простых числах, поднятых до некоторого интегрального показателя. Короче говоря, оказывается, что наименьшее общее кратное всех чисел ниже некоторого числа n равно произведению всех максимальных простых степеней ниже n .

Чтобы доказать это, мы начинаем с того, что думаем о свойствах, что x , наименьшее общее кратное всех чисел ниже n , должно иметь и выражать их в терминах простых степеней.

  1. x должен быть кратным всех простых степеней ниже n . Это очевидно; скажем n = 20 . 2 , 2 * 2 , 2 * 2 * 2 и 2 * 2 * 2 * 2 – все ниже 20 , поэтому все они должны делить x . Аналогично, 3 и 3 * 3 находятся ниже n и поэтому оба должны делить x .

  2. Если некоторое число a кратно главной степени p ** e , а p ** e – максимальная степень p ниже n , то a также кратно всем малым простым степеням p . Это также совершенно очевидно; если a == p * p * p , то a == (p * p) * p .

  3. По единственной теореме факторизации любое число m может быть выражено как кратное простым степеням меньше m . Если m меньше n , то m может быть выражено как кратное простым степеням, меньшим n .

Взятые вместе, два вторых наблюдения показывают, что любое число x , кратное всем максимальным простым степеням ниже n должно быть общим кратным всех чисел ниже n . В силу (2), если x кратно всем максимальным простым степеням ниже n , оно также кратно всем простым степеням ниже n . Таким образом, в силу (3) он также кратен всем остальным числам ниже n , так как они могут быть выражены как кратные максимальным степеням ниже n .

Наконец, учитывая (1), мы можем доказать, что x также является наименьшим общим кратным всех чисел ниже n , так как любое число, меньшее x не может быть кратным всех максимальных простых степеней ниже n и, следовательно, не может удовлетворять (1 ).

Результатом всего этого является то, что нам не нужно что-либо факторизовать. Мы можем просто генерировать простые числа меньше, чем n !

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

 prime_powers = [get_max_prime_power(p, n) for p in sieve(n)] result = reduce(operator.mul, prime_powers) 

Я останусь писать get_max_prime_power как упражнение. Быстрая версия в сочетании с вышесказанным может генерировать lcm всех чисел ниже 200000 за 3 секунды на моей машине.

Результат – 86871-значный номер!

Я получил решение в 0,066 миллисекундах (всего 74 спина через цикл), используя следующую процедуру:

Начните с наименьшего кратного для 1, что = 1. Затем найдите наименьший кратный для next_number_up. Сделайте это, добавив предыдущий наименьший кратный к себе (smallest_multiple = smallest_multiple + prev_prod) до next_number_up% smallest_multiple == 0. В этот момент smallest_multiple является правильным наименьшим кратным для next_number_up. Затем увеличивайте next_number_up и повторяйте до тех пор, пока не достигнете желаемого smallest_multiple (в этом случае 20 раз). Я считаю, что это находит решение в примерно n * log (n) времени (хотя, учитывая, как номера, похоже, работают, кажется, что они завершаются намного быстрее, чем обычно).

Например:

1 является наименьшим кратным для 1

Найти наименьшее количество для 2

Проверьте, работает ли предыдущий наименьший набор 1/2 = .5, поэтому нет

предыдущий мельчайший несколько + предыдущий наименьший множественный == 2.

Проверьте, является ли 2 делимым на 2 – да, поэтому 2 является наименьшим кратным для 2

Найти наименьшее количество для 3

Проверьте, работает ли предыдущий самый маленький многократный 2/3 = .667, поэтому нет

предыдущий наименьший несколько + предыдущий наименьший множественный == 4

Проверьте, является ли 4 делимым на 3 – нет

4 + предыдущий наименьший множественный == 6

Проверьте, является ли 6 делимым на 3 – да, поэтому 6 является наименьшим кратным для 3

Найти наименьшее количество для 4

Проверьте, работает ли предыдущий наименьший набор 6/4 = 1,5, поэтому нет

предыдущий наименьший множественный + предыдущий наименьший множественный == 12

Проверьте, является ли 12 делимым на 4 – да, поэтому 12 является наименьшим кратным для 4

повторить до 20 ..

Ниже приведен код в Ruby, реализующий этот подход:

 def smallestMultiple(top) prod = 1 counter = 0 top.times do counter += 1 prevprod = prod while prod % counter != 0 prod = prod + prevprod end end return prod end 

Это решение работает довольно быстро для меня (импортирует numpy).

 t0 = time.time() import numpy ints = numpy.array(range(1,21)) primes = [2,3,5,7,11,13,17,19] # under 20 facts = [] for p in primes: counter = 0 nums = ints while any(nums % p == 0): nums = nums / float(p) counter += 1 facts.append(counter) facts = numpy.array(facts) mults = primes**facts ans = 1 for m in mults: ans = m * ans t1 =time.time() perf = t1 - t0 print "Problem 5\nAnswer:",ans, "runtime:", perf, "seconds" """Problem 5 Answer: 232792560 runtime: 0.00505399703979 seconds""" 

Я написал решение для euler5, что:

  • На порядок выше, чем большинство решений здесь, когда n = 20 (хотя не все респонденты сообщают о своем времени), потому что он не использует импорт (кроме измерения времени для этого ответа) и только базовые структуры данных в python.
  • Весы намного лучше, чем большинство других решений. Он даст ответ для n = 20 за 6e-05 секунд или для n = 100 за 1 миллисекунду быстрее, чем большинство ответов для n = 20, перечисленных здесь.

     import time a=time.clock() # set timer j=1 factorlist=[] mydict={} # change second number to desired number +1 if the question were changed. for i in range(2,21,1): numberfactors=[] num=i j=2 # build a list of the prime factors for j in range(j,num+1,1): counter=0 if i%j==0: while i%j==0: counter+=1 numberfactors.append(j) i=i/j # add a list of factors to a dictionary, with each prime factor as a key if j not in mydict: mydict[j] = counter # now, if a factor is already present n times, including n times the factor # won't increase the LCM. So replace the dictionary key with the max number of # unique factors if and only if the number of times it appears is greater than # the number of times it has already appeared. # for example, the prime factors of 8 are 2,2, and 2. This would be replaced # in the dictionary once 16 were found (prime factors 2,2,2, and 2). elif mydict[j] < counter: mydict[j]=counter total=1 for key, value in mydict.iteritems(): key=int(key) value=int(value) total=total*(key**value) b=time.clock() elapsed_time=ba print total, "calculated in", elapsed_time, "seconds" 

    возвращает:

     232792560 calculated in 6e-05 seconds # does not rely on heuristics unknown to all users, for instance the idea that # we only need to include numbers above 10, etc. # For all numbers evenly divisible by 1 through 100: 69720375229712477164533808935312303556800 calculated in 0.001335 seconds 

Вот программа на языке C. ура

 #include <stdio.h> #include <stdlib.h> //2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. //What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? bez_ost(int q) { register br=0; for( register i=1;i<=20;i++) if(q%i==0) br++; if(br==20) return 1; return 0; } int main() { register j=20; register ind=0; while(ind!=1) { j++; if(bez_ost(j)) break; } fprintf(stdout,"\nSmallest positive number that is evenlu divisible by all of the numbers from 1 to 20 is: %d\n\a",j); system("Pause"); } в #include <stdio.h> #include <stdlib.h> //2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. //What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? bez_ost(int q) { register br=0; for( register i=1;i<=20;i++) if(q%i==0) br++; if(br==20) return 1; return 0; } int main() { register j=20; register ind=0; while(ind!=1) { j++; if(bez_ost(j)) break; } fprintf(stdout,"\nSmallest positive number that is evenlu divisible by all of the numbers from 1 to 20 is: %d\n\a",j); system("Pause"); } 

У меня была та же проблема. Алгоритм кажется довольно медленным, но тем не менее он работает.

 result = list() xyz = [x for x in range(11, 21)] number = [2520] count = 0 while len(result) == 0: for n in number: print n for x in xyz: if n % x == 0: count += 1 elif n % x != 0: count = 0 break if count == 10: result.append(number[0]) elif count != 10: number[0] += 1 print result 

Это был алгоритм, который я сделал.

Разделите число как основную факторизацию.

Все простые числа менее 20:

 2,3,5,7,11,13,17,19 

Таким образом, минимальное количество, которое можно разделить на эти числа:

 2*3*5*7*11*13*17*19 

композиты:

 4,6,8,9,10,12,14,15,16,18,20 = 2^2, 2*3, 2^3, 3^2, 2*5, 2^2*3, 2*7, 3*5, 2*3^2, 2^2*5 

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

  • 2^3 для построения 4, 8, и 16
  • 3 построить 9
  • Первичная факторизация: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560

Как насчет этого? Требуемое число – это, в конце концов, LCM данных чисел.

 def lcm(a,b): lcm1 = 0 if a == b: lcm1 = a else: if a > b: greater = a else: greater = b while True: if greater % a == 0 and greater % b == 0: lcm1 = greater break greater += 1 return lcm1 import time start_time = time.time() list_numbers = list(range(2,21)) lcm1 = lcm(list_numbers[0],list_numbers[1]) for i in range(2,len(list_numbers)): lcm1 = lcm(lcm1,list_numbers[i]) print(lcm1) print('%0.5f'%(time.time()-start_time)) 

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

 import time primes = [11,13,17,19] composites = [12,14,15,16,18,20] def evenlyDivisible(target): evenly = True for n in composites: if target % n > 0: evenly = False break return evenly step = 1 for p in primes: step *= p end = False number = 0 t1 = time.time() while not end: number += step if evenlyDivisible(number): end = True print("Smallest positive evenly divisible number is",number) t2 = time.time() print("Time taken =",t2-t1) 

Выполнено за 0,06 секунды

Я думаю, что это ответ:

 primes = [11, 13, 17, 19] result = 2520 for i in primes: result *= i print (result * 2) 

Здесь я также сделал, используя простой способ факторизации.

 #!/usr/bin/env python import math def is_prime(num): if num > 1: if num == 2: return True if num%2 == 0: return False for i in range(3, int(math.sqrt(num))+1, 2): if num%i == 0: return False return True return False def lcm(number): prime = [] lcm_value = 1 for i in range(2,number+1): if is_prime(i): prime.append(i) final_value = [] for i in prime: x = 1 while i**x < number: x = x + 1 final_value.append(i**(x-1)) for j in final_value: lcm_value = j * lcm_value return lcm_value if __name__ == '__main__': print lcm(20) 

После проверки того, сколько времени прошло, это было неплохо.

root @ l-g6z6152: ~ / learn / project_euler # время python lcm.py

 232792560 real 0m0.019s user 0m0.008s sys 0m0.004s 

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

 describe(`2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?`, () => { it("prooves the example: 10", () => smallestWithoutRemainder(10).should.be.equal(2520)); it("prooves 1", () => smallestWithoutRemainder(1).should.be.equal(1)); it("prooves 2", () => smallestWithoutRemainder(2).should.be.equal(2)); it("prooves 3", () => smallestWithoutRemainder(3).should.be.equal(6)); it("prooves 4", () => smallestWithoutRemainder(4).should.be.equal(12)); it("prooves 5", () => smallestWithoutRemainder(5).should.be.equal(60)); it("prooves 6", () => smallestWithoutRemainder(6).should.be.equal(60)); it("prooves 7", () => smallestWithoutRemainder(7).should.be.equal(420)); it("prooves 8", () => smallestWithoutRemainder(8).should.be.equal(840)); it("prooves 9", () => smallestWithoutRemainder(9).should.be.equal(2520)); it("prooves 12", () => smallestWithoutRemainder(12).should.be.equal(27720)); it("prooves 20", () => smallestWithoutRemainder(20).should.be.equal(232792560)); it("prooves 30", () => smallestWithoutRemainder(30).should.be.equal(2329089562800)); it("prooves 40", () => smallestWithoutRemainder(40).should.be.equal(5342931457063200)); }); let smallestWithoutRemainder = (end: number, interval?: number) => { // What do we know? // - at 10, the answer is 2520 // - can't be smaller than the lower multiple of 10 // - must be an interval of the lower multiple of 10 // so: // - the interval and the start should at least be divisable by 'end' // - we can recurse and build on the results before it. if (!interval) interval = end; let count = Math.floor(end / 10); if (count == 1) interval = 2520; else if (count > 1) interval = smallestWithoutRemainder((count - 1) * 10, interval); for (let i = interval; true; i += interval) { let failed = false; for (let j = end; j > 1; j--) { if (i % j != 0) { failed = true; break; } } if (!failed) return i; } } 
  • Лучший способ «очистить» html-текст
  • Найти подпоследовательности строк в строках
  • Как отложить задачу с помощью Celery?
  • Python: как найти второе наибольшее число в списке?
  • Как я могу избавиться от значений None в словаре?
  • Как сохранить сгенерированный PDF-файл с Reportlab в хранилище данных в App Engine Python
  • Как создать функцию, которая подсчитывает, сколько раз каждый элемент равен 2 элементам справа
  • Что делать, если я хочу сохранить значение None в memcache?
  • Python - лучший язык программирования в мире.