Optimizing the Prime Number Search Algorithm in Python3

Question:

How can you increase the speed of searching for prime numbers in the range from M to N by the "Sieve of Eratosphet" method for large numbers / ranges?

import math

def getPrimes(M, N):
  N += 1
  sieve = set(range(2, N))
  for i in range(2, int(math.sqrt(N))):
    if i in sieve:
      sieve -= set(range(2*i, N, i))

  return sorted(i for i in sieve if i >= M) # Особенно смущает эта строка

Testing performance:

from timeit import timeit

print('Время выполнения:', timeit(lambda: getPrimes(1000000, 5000000), number=1), 'сек')

# Время выполнения: 5.557504795000568 сек

Answer:

I managed to slightly optimize the original algorithm:

import math
from timeit import timeit


def getPrimes_optimized(M, N):

    N += 1
    sieve = set(range(3, N, 2))  # пропускаем четные, т.к. кроме 2 - простых четных чисел не бывает
    sieve.add(2)  # добавляем двойку по вышеуказанной причине

    for i in range(3, int(math.sqrt(N)), 2):  # тоже самое, поэтому начинаем итерировать с тройки с шагом 2
        if i in sieve:
            sieve -= set(range(2*i, N, i))

    return sorted(i for i in sieve if M <= i)


print(getPrimes_optimized(1000000, 5000000) == getPrimes(1000000, 5000000))

print('Время выполнения:', timeit(lambda: getPrimes_optimized(1000000, 5000000), number=10), 'сек')
print('Время выполнения:', timeit(lambda: getPrimes(1000000, 5000000), number=10), 'сек')

Shows the following output on my computer:

True  #  полученные списки идентичны
Время выполнения: 23.673116489000677 сек  # мой оптимизированный вариант с number=10
Время выполнения: 33.008412028997554 сек  # оригинальный вариант с number=10
Scroll to Top