Python Eratosthenes Sieve Algorithm Optimization

primes sieve-of-eratosthenes

Question

Estoy intentando implementar el Tamiz de Eratóstenes. La salida parece ser correcta (menos "2" que se debe agregar) pero si la entrada a la función es mayor que 100k o así parece tomar una cantidad de tiempo desproporcionada. ¿De qué maneras puedo optimizar esta función?

def sieveErato(n):
     numberList = range(3,n,2)

     for item in range(int(math.sqrt(len(numberList)))):
            divisor = numberList[item]
            for thing in numberList:
                    if(thing % divisor == 0) and thing != divisor:
                            numberList.remove(thing)
    return numberList

Answer 1

Advertencia: eliminar elementos de un iterador mientras se itera puede ser peligroso ...

Podrías hacer el

    if(thing % divisor == 0) and thing != divisor:

prueba el encendedor dividiéndolo en el ciclo que se rompe cuando llegas al índice de ''divisor'' y luego la prueba:

for thing in numberList_fromDivisorOn:
    if(thing % divisor == 0):
        numberList.remove(thing)

Answer 2

Este código tarda 2 segundos en generar números primos inferiores a 10M (no es mío, lo encontré en alguna parte de google)

def erat_sieve(bound):
    if bound < 2:
        return []
    max_ndx = (bound - 1) // 2
    sieve = [True] * (max_ndx + 1)
    #loop up to square root
    for ndx in range(int(bound ** 0.5) // 2):
        # check for prime
        if sieve[ndx]:
            # unmark all odd multiples of the prime
            num = ndx * 2 + 3
            sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
    # translate into numbers
    return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]

Answer 3

Puedes intentarlo de la misma manera que lo hizo Eratóstenes. Tome una matriz con todos los números que necesita para verificar el orden ascendente, vaya al número 2 y márquelo. Ahora rasca cada segundo número hasta el final de la matriz. Luego ve a 3 y márcalo. Después de eso, rasca cada tercer número. Luego vaya a 4 - ya está rayado, así que sáltelo. Repita esto para cada n + 1 que no esté rayado.

Al final, los números marcados son los principales. Este algoritmo es más rápido, pero a veces necesita mucha memoria. Puede optimizarlo un poco, soltando todos los números pares (porque no son primos) y agregue 2 manualmente a la lista. Esto cambiará la lógica un poco, pero tomará la mitad de la memoria.

Aquí hay una ilustración de lo que estoy hablando: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 4

Tu algoritmo no es el Tamiz de Eratóstenes. Usted realiza la división de prueba (el operador de módulo) en lugar de los múltiplos de cruce, como lo hizo Eratóstenes hace más de dos mil años. Aquí hay una explicación del verdadero algoritmo de cribado, y se muestra a continuación es mi implementación simple y directa, que devuelve una lista de primos que no excede n :

def sieve(n):
    m = (n-1) // 2
    b = [True]*m
    i,p,ps = 0,3,[2]
    while p*p < n:
        if b[i]:
            ps.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i+=1; p+=2
    while i < m:
        if b[i]:
            ps.append(p)
        i+=1; p+=2
    return ps

Solo tamizamos los números impares, deteniéndonos en la raíz cuadrada de n . Los cálculos de aspecto extraño en el mapa j entre los números enteros que se tamizan 3, 5, 7, 9, ... y los índices 0, 1, 2, 3, ... en la matriz b de bits.

Puede ver esta función en acción en http://ideone.com/YTaMB , donde calcula los números primos a un millón en menos de un segundo.

Answer 5

si se le da memoria y tiempo ilimitados, el siguiente código imprimirá todos los números primos. y lo hará sin usar la división de prueba. se basa en el código haskell en el documento: El tamiz genuino de Eratosthenes por Melissa E. O''Neill

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: print p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p, n,o,p))
    print p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p, n,o,p))
            print p
            continue
        while t[0][0] <= p:
            _, b,c,d = t[0]
            b,c = b+w[c],(c+1)%l
            heapreplace(t, (b*d, b,c,d))
sieve()

Answer 6

Seguí este enlace: Tamiz de Eratóstenes - Encontrando Primes Python como lo sugirió @MAK y encontré que la respuesta aceptada podría mejorarse con una idea que he encontrado en su código:

def primes_sieve2(limit):
    a = [True] * limit               # Initialize the primality list
    a[0] = a[1] = False
    sqrt = int(math.sqrt(limit))+1
    for i in xrange(sqrt):
        isprime = a[i]
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False
    for (i, isprime) in enumerate(a[sqrt:]):
        if isprime:
            yield i+sqrt