Почему мое Сито Эратосфена работает так медленно?

Я пишу программу простых чисел на Python для Сита Эратосфена. Хотя это похоже на работу, но очень медленно. Как я могу ускорить это?

primes = []
upperLimit = 1000

for x in range(2,upperLimit):
  primes.append(x)
for y in range(0,int(len(primes)**0.5)):
  remove = []
  for j in range(primes[y]**2,upperLimit,primes[y]):
    remove.append(j)
  for i in remove:
    if i in primes:
      primes.remove(i)

print(primes)

Обновление: благодаря помощи из ответов я переписал код, используя логические значения, а не числа. Список ниже 100000 теперь выполняется менее чем за 6 секунд.

i = 2
limit = 100000
primes = [True] * limit
primes[0] = False
while i < limit**0.5:
    if primes[i-1]:
        for x in range(i * 2, limit + 1,i):
            primes[x-1] = False
    i += 1
count = 1
total = []
for i in primes:
    if i:
        total.append(count)
    count += 1
print(total)
Источник

2 ответа

Решение

Я считаю, что основной неэффективностью в вашем коде является list простых чисел, которые вы поддерживаете. Хотя это не может быть очевидным, призывая primes.remove это очень дорогая операция. Нужно пройти через list чтобы попытаться найти значение, которое вы удаляете, а затем он должен изменить list перемещая все элементы после того, что вы ищете.

Например

l = [0, 1, 2, 3, 4]
l.remove(5)  # This has to look at all the elements in l, since 6 isn't there
l.remove(0)  # This finds 1 quickly but then has to move every element to the left

Более традиционный подход к Сите Эратосфена состоит в использовании массива (list в Python) из всех чисел, которые вы рассматриваете, где каждый элемент является логическим значением, указывающим, может ли число быть простым.

Подражая приведенному выше примеру:

l = [True, True, True, True, True]
l[0] = False  # Just goes straight to that element and changes its value

Вот пример того, как написать этот код:

primes = [True] * 100000

# We already know 2 is the first prime
primes[0] = False
primes[1] = False

# Fine to stop at sqrt(len(primes)) here as you're already doing    
for i in range(2, len(primes)):
    if primes[i]:
        for j in range(i**2, len(primes), i):
            primes[j] = False

print([n for n, is_prime in enumerate(primes) if is_prime])

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

Источник

Это медленно, потому что есть много операций, которые вы делаете гораздо чаще, чем нужно. продолжительность жизни составного числа N выглядит примерно так:

  • добавить N к простым числам
  • для каждого небольшого числа I (
  • Добавить все большие кратные I, чтобы удалить
  • за каждого я в удалении
    • если я все еще в простых числах, удалите его.

    • Это много "штрихов" для каждого номера. Это также много маленьких чисел, чтобы рассмотреть.

    Вместо этого попробуйте это:

    • Составьте список логических значений (все True), по одному на каждое потенциальное простое число.
    • В то время как самое низкое значение я отметил True
    • Очистить (включить Ложь) все большие кратные I
    • Примечание: не пытайтесь проверить, является ли значение уже ложным

    На этом этапе ваши простые числа - это точно те значения, которые все еще отмечены как True

    Источник
    Другие вопросы по тегам