Как сделать Решето Эратосфена быстрее?

Я пытаюсь решить 10-ю проблему в Project Euler. Он состоит в нахождении суммы всех простых чисел меньше двух миллионов. Я написал следующий код на основе решета Эратосфена.

import time
t0 = time.time()
n=200000
liste=list(range(2,n))
k=2
s=2
while k <=n:
    liste=list(set(liste)-set(range(k,n,k)))
    if liste!=[]:
        k=min(liste)
        s+=k
    else:
        break
print(s)
t1 = time.time()
total = t1-t0
print(total)

Я протестировал приведенный выше код для n=200000, но он слишком медленный для n=2000000. Я был бы очень благодарен за любую помощь в улучшении этой программы.


python-3.x python primes sieve-of-eratosthenes number-theory
person Driss Alami    schedule 17.06.2015    source источник
comment
stackoverflow.com/a/23423821/2141635 используйте сумму, и у вас есть ответ   -  person Padraic Cunningham    schedule 17.06.2015
comment
Также связано: stackoverflow.com/q/2068372/1639625   -  person tobias_k    schedule 17.06.2015
comment
по теме: Ускорить операции с битовыми строками/битами в Python?   -  person jfs    schedule 17.06.2015
comment
просто замените while k <=n на while k <=(n/k) и покончите с этим (конечно, теперь вы получите непустое liste, которое на данный момент будет содержать только простые числа!).   -  person Will Ness    schedule 19.06.2015
comment
@will Ness Спасибо, это работает, это намного быстрее, чем у меня. Однако это все еще слишком медленно для $n=2000000$.   -  person Driss Alami    schedule 22.06.2015
comment
@DrissAlami: что значит слишком медленно (используйте количество миллисекунд на вашем оборудовании)? Какие функции вы пробовали из этого ответа?   -  person jfs    schedule 22.06.2015
comment
Я отозвал свой закрытый голос (рабочий код, принадлежит Code Review). Я подумал, что код был настолько медленным, что функционально он не работал.   -  person Will Ness    schedule 23.06.2015

Ответы (2)


arrow_upward
0
arrow_downward

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

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

    sete.difference_update(range(p*p,n,p*2))

Чтобы найти минимальный элемент, вы можете просто вызвать min(sete) в наборе, преобразование списка не требуется.

Из-за неэффективного поиска элемента min общая сложность результирующего кода будет приближаться к n^1.5, что не слишком хорошо, но и не слишком ужасно. В частности, на ideone.com он завершается менее чем за 4,9 секунды, находя сумму для простых чисел меньше 2000000, и 0,5 секунды для 400000 (с дополнительной оптимизацией работы только с коэффициентами, в первую очередь).

person Will Ness    schedule 22.06.2015

arrow_upward
0
arrow_downward

Для нахождения суммы простых чисел ниже 200000 приведенный ниже код (с использованием сита эратосфена) работает намного быстрее. Ваш код занимает почти 55 секунд, тогда как приведенный ниже код выполняется всего за 0,8 секунды!

import time
t0 = time.time()
n = 200000
sieve = [True] * (n + 1)
for i in range(2, n + 1) :
  if sieve[i] :
     for mult in range(i + i, n + 1, i) :
        sieve[mult] = False
s=0     
for i in range(2,n + 1):
    if sieve[i] :
        s+=i    
print(s)
t1 = time.time()
total = t1-t0
print(total)
person Sanjana S    schedule 21.06.2015