¿Por qué mi aplicación del tamiz de Atkin números con vistas cerca del límite especificado?
-
25-09-2019 - |
Pregunta
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.
Solución
- Cambiar
lim
alimit
. Por supuesto, usted debe haber sabido. -
Desde
sieve = [False]*limit
, el mayor índice permitido eslimit-1
.Sin embargo, en esta línea
if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
Está comprobando si
n<=limit
. Sin==limit
continuaciónsieve[n]
plantea una IndexError. Pruebe su algoritmo con un valor pequeño delimit
(por ejemplo n = 50). Verá este error viene para arriba. Una solución fácil es usarsieve = [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 ensieve
por uno. (Por ejemplo, el cambiosieve[n]
asieve[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 demath.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