¿Por qué mi aplicación del tamiz de Atkin números con vistas cerca del límite especificado?

Question

Mi implementación de tamiz de Atkin ya sea miradores primos cercanos al límite o compuestos cerca del límite . mientras que algunos límites funcionan y otras no. Estoy Estoy completamente confundido en cuanto a lo que está mal.

def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
    for j in range(1, factor):
        n = 4*i**2+j**2
        if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
            sieve[n] = not sieve[n]
        n = 3*i**2+j**2
        if (n <= lim) and (n % 12 == 7):
            sieve[n] = not sieve[n]
        if i>j:
            n = 3*i**2-j**2
            if (n <= lim) and (n % 12 == 11):
                sieve[n] = not sieve[n]
for index in range(5,factor):
    if sieve[index]:
        for jndex in range(index**2, limit, index**2):
            sieve[jndex] = False
for index in range(7,limit):
    if sieve[index]:
        results.append(index)
return results

Por ejemplo, cuando generan una primos hasta el límite de 1000, el tamiz Atkin pierde el primer 997, pero incluye el compuesto 965. Pero si genero hasta el límite de 5000, la lista que devuelve es completamente correcto.

Answer 1

• Cambiar lim a limit. Por supuesto, usted debe haber sabido.
• Desde sieve = [False]*limit, el mayor índice permitido es limit-1.

  Sin embargo, en esta línea

  if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
  

  Está comprobando si n<=limit. Si n==limit continuación sieve[n] plantea una IndexError. Pruebe su algoritmo con un valor pequeño de limit (por ejemplo n = 50). Verá este error viene para arriba. Una solución fácil es usar

  sieve = [False]*(limit+1)
  

  La solución fácil es un desperdicio poco desde tamiz [0] nunca se utiliza. Así que se podría pensar en una solución mejor es mantener sieve = [False]*limit, pero arreglar todo su otro código escalonando el índice en sieve por uno. (Por ejemplo, el cambio sieve[n] a sieve[n-1] todas partes, etc.) Sin embargo, esto le obligará a hacer una serie de sustracciones amplio lo cual no será bueno para la velocidad. Así que la solución fácil / desperdicio es en realidad, probablemente la mejor opción.

• Según http: //en.wikipedia. org / wiki / Sieve_of_Atkin , x debe ser un número entero en [1, sqrt (límite)], incluyendo los puntos finales.

  En el código

  factor = int(math.sqrt(limit))
  

  y int toma el suelo de math.sqrt(limit). Además,

  range(1,factor) va de 1 a factor-1 de. Por lo que son de por 1.

  Así que hay que cambiar esto a

  factor = int(math.sqrt(limit))+1
  

• Consulte la forma más rápida para listar todos los números primos por debajo de N de una alternativa (y más rápido) la aplicación del tamiz de Atkin, debido a Steve Krenzel.

def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results