Tamiz de implementación de Atkin en Python
Estoy tratando de implementar el algoritmo de Sieve of Atkin que se proporciona en Wikipedia Link de la siguiente manera:
Lo que he probado hasta ahora es la implementación en Python dada por el siguiente código:
import math
is_prime = list()
limit = 100
for i in range(5,limit):
is_prime.append(False)
for x in range(1,int(math.sqrt(limit))+1):
for y in range(1,int(math.sqrt(limit))+1):
n = 4*x**2 + y**2
if n<=limit and (n%12==1 or n%12==5):
# print "1st if"
is_prime[n] = not is_prime[n]
n = 3*x**2+y**2
if n<= limit and n%12==7:
# print "Second if"
is_prime[n] = not is_prime[n]
n = 3*x**2 - y**2
if x>y and n<=limit and n%12==11:
# print "third if"
is_prime[n] = not is_prime[n]
for n in range(5,int(math.sqrt(limit))):
if is_prime[n]:
for k in range(n**2,limit+1,n**2):
is_prime[k] = False
print 2,3
for n in range(5,limit):
if is_prime[n]: print n
Ahora recibo un error como
is_prime[n] = not is_prime[n]
IndexError: list index out of range
Esto significa que estoy accediendo al valor en la lista donde el índice es mayor que la longitud de la lista. Considere la Condición cuando x, y = 100, entonces, por supuesto, la condición n = 4x ^ 2 + y ^ 2 dará un valor que es mayor que la longitud de la lista. ¿Estoy haciendo algo mal aquí? Por favor ayuda.
EDITAR 1 Como sugirió Gabe, usando
is_prime = [False] * (limit + 1)
en lugar de:
for i in range(5,limit):
is_prime.append(False)
resolvió el problema