python 3.x - Optimizar el tamiz de Eratóstenes aún más

python-3.x optimization

Question

Creo que escribí un Tamiz de Eratóstenes, pero parece que no está tan optimizado como podría estarlo. Funciona y obtiene todos los números primos hasta N, pero no tan rápido como esperaba. Todavía estoy aprendiendo Python, proveniente de dos años de Java, así que si algo no es particularmente Pythonic, me disculpo:

def sieve(self):
is_prime = [False, False, True, True] + [False, True] * ((self.lim - 4) // 2)
for i in range(3, self.lim, 2):
if i**2 > self.lim: break
if is_prime[i]:
for j in range(i * i, self.lim, i * 2):
is_prime[j] = False
return is_prime

He visto otras preguntas similares a esta, pero no puedo entender cómo algunas de las optimizaciones más complicadas encajarían en mi código. ¿Alguna sugerencia?

EDITAR: según lo solicitado, algunas de las otras optimizaciones que he visto están deteniendo la iteración del primer bucle for antes del límite, y saltando por diferentes números, lo que creo que es la optimización de la rueda.

EDITAR 2: Aquí está el código que utilizaría el método, para Padraic:

primes = sieve.sieve()
for i in range(0, len(primes)):
if primes[i]:
print("{:d} ".format(i), end = '''')
print() # print a newline

Answer 1

un enfoque ligeramente diferente: use un bitarray para representar los números impares 3,5,7,... ahorrando espacio en comparación con una lista de booleanos.

Esto puede ahorrar algo de espacio solamente y no ayudar a acelerar ...

from bitarray import bitarray
def index_to_number(i): return 2*i+3
def number_to_index(n): return (n-3)//2
LIMIT_NUMBER = 50
LIMIT_INDEX = number_to_index(LIMIT_NUMBER)+1
odd_primes = bitarray(LIMIT_INDEX)
# index 0 1 2 3
# number 3 5 7 9
odd_primes.setall(True)
for i in range(LIMIT_INDEX):
if odd_primes[i] is False:
continue
n = index_to_number(i)
for m in range(n**2, LIMIT_NUMBER, 2*n):
odd_primes[number_to_index(m)] = False
primes = [index_to_number(i) for i in range(LIMIT_INDEX)
if odd_primes[i] is True]
primes.insert(0,2)
print(''primes: '', primes)

la misma idea otra vez; pero esta vez deje que bitarray maneje el bucle interno usando la asignación de corte. Esto puede ser más rápido.

for i in range(LIMIT_INDEX):
if odd_primes[i] is False:
continue
odd_primes[2*i**2 + 6*i + 3:LIMIT_INDEX:2*i+3] = False

(¡ninguno de este código ha sido revisado seriamente! úselo con cuidado)

en caso de que esté buscando un generador de primos basado en un método diferente ( factorización de rueda ), eche un vistazo a esta excelente respuesta .