Просто, чтобы уточнить, это не проблема домашней работы:)
Я хотел найти простые числа для математического приложения, которое я создаю, и наткнулся на Сито Эратосфена.
Я написал реализацию в 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)
UPDATE: Я закончил делать профилирование этого кода и обнаружил, что довольно много времени было потрачено на удаление элемента из списка. Совершенно понятно, что нужно перебирать весь список (наихудший вариант), чтобы найти элемент, а затем удалить его, а затем скорректировать список (возможно, какая-то копия продолжается?). Во всяком случае, я выбрал список для словаря. Моя новая реализация -
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = 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[i]==True]
print primes_sieve1(2000000)