Решето Эратосфена - В поисках простых чисел Python ⇐ Python

[Anonymous]

Просто поясню: это не домашнее задание

Я хотел найти простые числа для математического приложения, которое создаю, и наткнулся на подход Решето Эратосфена.

Я написал реализацию на Python. Но это ужасно медленно. Например, если я хочу найти все простые числа меньше 2 миллионов. Это занимает > 20 минут. (Я остановил это на этом этапе). Как я могу это ускорить?

def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)

for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes

print primes_sieve(2000)


ОБНОВЛЕНИЕ:
В итоге я выполнил профилирование этого кода и обнаружил, что довольно много времени было потрачено на удаление элемента из списка. Вполне понятно, учитывая, что ему приходится пройти весь список (в худшем случае), чтобы найти элемент, затем удалить его, а затем перенастроить список (может быть, какая-то копия продолжается?). В любом случае, я выбросил список для словаря. Моя новая реализация -

def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes = True

for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes==True]

print primes_sieve1(2000000)


Подробнее здесь: https://stackoverflow.com/questions/393 ... mes-python