python - primeros - Tamiz de Eratóstenes-Primos entre X y N

encontrar los numeros primos hasta un numero python

Question

Encontré esta implementación altamente optimizada de Sieve of Eratosthenes para Python en Stack Overflow. Tengo una idea aproximada de lo que está haciendo, pero debo admitir que los detalles de su funcionamiento me eluden.

Todavía me gustaría usarlo para un pequeño proyecto (soy consciente de que hay bibliotecas para hacer esto, pero me gustaría usar esta función).

Aquí está el original:

''''''
    Sieve of Eratosthenes 
    Implementation by Robert William Hanks      
    https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188
''''''

def sieve(n):
    """Return an array of the primes below n."""
    prime = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool)
    for i in range(3, int(n**.5) + 1, 3):
        if prime[i // 3]:
            p = (i + 1) | 1
            prime[       p*p//3     ::2*p] = False
            prime[p*(p-2*(i&1)+4)//3::2*p] = False
    result = (3 * prime.nonzero()[0] + 1) | 1
    result[0] = 3
    return numpy.r_[2,result]

Lo que estoy tratando de lograr es modificarlo para devolver todos los números primos debajo de n comenzando en x para que:

primes = sieve(50, 100)

devolvería números primos entre 50 y 100. Esto parecía bastante fácil, traté de reemplazar estas dos líneas:

def sieve(x, n):
    ...
    for i in range(x, int(n**.5) + 1, 3):
    ...

Pero por una razón que no puedo explicar, ¡el valor de x en lo anterior no tiene influencia en la matriz numpy devuelta!

¿Cómo puedo modificar el sieve() para que solo devuelva números primos entre x y n

Answer 1

La implementación que ha pedido prestado puede comenzar en 3 porque reemplaza el tamizado de los múltiplos de 2 al omitir todos los números pares; eso es lo que hacen los 2*… que aparecen varias veces en el código. El hecho de que 3 sea el próximo primo también está codificado por todos lados, pero ignorémoslo por el momento, porque si no puedes pasar el casquillo especial de 2, no importa la carcasa especial de 3 .

Saltarse los números pares es un caso especial de una "rueda". Puede omitir el tamizado de múltiplos de 2 aumentando siempre en 2; puede omitir el tamizado de múltiplos de 2 y 3 aumentando alternativamente en 2 y 4; puede omitir el tamizado de múltiplos de 2, 3, 5 y 7 aumentando alternativamente en 2, 4, 2, 4, 6, 2, 6, ... (hay 48 números en la secuencia), y así sucesivamente. Por lo tanto, podría ampliar este código encontrando primero todos los números primos hasta x , luego construyendo una rueda, y luego usando esa rueda para encontrar todos los números primos entre x y n .

Pero eso agrega mucha complejidad. Y una vez que llega demasiado más allá de 7, el costo (tanto en tiempo como en espacio para almacenar la rueda) inunda los ahorros. Y si tu objetivo no es encontrar los números primos antes de x , encontrar los números primos antes de x para que no tengas que encontrarlos parece algo tonto. :)

Lo más simple es encontrar todos los números primos hasta n , y descartar los que están debajo de x . Que puedes hacer con un cambio trivial al final:

primes = numpy.r_[2,result]
return primes[primes>=x]

O, por supuesto, hay formas de hacerlo sin perder el almacenamiento de los primos iniciales que va a tirar. Sería un poco complicado trabajar en este algoritmo (probablemente quieras construir la matriz en secciones, luego descartar cada sección que sea completamente < x medida que avanzas, luego apilar todas las secciones restantes); sería mucho más fácil usar una implementación diferente del algoritmo que no está diseñada para la velocidad y la simplicidad sobre el espacio ...

Y, por supuesto, hay diferentes algoritmos de búsqueda de primos que no requieren enumerar todos los primos hasta x en primer lugar. Pero si desea utilizar esta implementación de este algoritmo, eso no importa.

Answer 2

Como ahora está interesado en buscar otros algoritmos u otras implementaciones, intente con este. No usa numpy, pero es bastante rápido. He intentado algunas variaciones sobre este tema, incluido el uso de conjuntos y el cálculo previo de una tabla de números bajos primos, pero todos fueron más lentos que este.

#! /usr/bin/env python

'''''' Prime range sieve.

    Written by PM 2Ring 2014.10.15

    For range(0, 30000000) this is actually _faster_ than the 
    plain Eratosthenes sieve in sieve3.py !!!
''''''

import sys

def potential_primes():
    '''''' Make a generator for 2, 3, 5, & thence all numbers coprime to 30 ''''''
    s = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
    for i in s:
        yield i
    s = (1,) + s[3:] 
    j = 30
    while True:
        for i in s:
            yield j + i
        j += 30


def range_sieve(lo, hi):
    '''''' Create a list of all primes in the range(lo, hi) ''''''

    #Mark all numbers as prime
    primes = [True] * (hi - lo)

    #Eliminate 0 and 1, if necessary
    for i in range(lo, min(2, hi)):
        primes[i - lo] = False

    ihi = int(hi ** 0.5)
    for i in potential_primes():
        if i > ihi: 
            break

        #Find first multiple of i: i >= i*i and i >= lo
        ilo = max(i, 1 + (lo - 1) // i ) * i

        #Determine how many multiples of i >= ilo are in range
        n = 1 + (hi - ilo - 1) // i

        #Mark them as composite
        primes[ilo - lo : : i] = n * [False]

    return [i for i,v in enumerate(primes, lo) if v]


def main():
    lo = int(sys.argv[1]) if len(sys.argv) > 1 else 0
    hi = int(sys.argv[2]) if len(sys.argv) > 2 else lo + 30
    #print lo, hi

    primes = range_sieve(lo, hi)
    #print len(primes)
    print primes
    #print primes[:10], primes[-10:]


if __name__ == ''__main__'':
    main()

Y aquí hay un enlace al filtro simple de Eratosthenes que mencioné en el docstring, en caso de que quiera comparar este programa con ese.

Puede mejorar esto ligeramente al deshacerse del ciclo bajo #Eliminate 0 and 1, if necessary . Y supongo que podría ser un poco más rápido si evitas mirar los números pares; ciertamente usaría menos memoria. Pero entonces tendrías que manejar los casos cuando 2 estaba dentro del rango, y creo que mientras menos pruebas tengas, más rápido se ejecutará esto.

Aquí hay una pequeña mejora de ese código: reemplazar

    #Mark all numbers as prime
    primes = [True] * (hi - lo)

    #Eliminate 0 and 1, if necessary
    for i in range(lo, min(2, hi)):
        primes[i - lo] = False

con

    #Eliminate 0 and 1, if necessary
    lo = max(2, lo)

    #Mark all numbers as prime
    primes = [True] * (hi - lo)

Sin embargo, la forma original puede ser preferible si desea devolver la lista simple de bool lugar de realizar la enumerate para compilar una lista de enteros: la lista bool es más útil para probar si un número dado es primo; OTOH, el enumerate podría usarse para construir un conjunto en lugar de una lista.