Peneira de implementação Atkin em Python
Eu estou tentando implementar o algoritmo de peneira de Atkin, dado no Wikipedia Link como abaixo:
O que eu tentei até agora é a implementação em Python fornecida pelo seguinte 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
Agora eu recebo erro como
is_prime[n] = not is_prime[n]
IndexError: list index out of range
isso significa que estou acessando o valor na lista em que o índice é maior que o comprimento da lista. Considere a Condição quando x, y = 100, é claro que a condição n = 4x ^ 2 + y ^ 2 fornecerá um valor maior que o comprimento da lista. Estou fazendo algo errado aqui? Por favor ajude.
EDIT 1 Conforme sugerido por Gabe, usar
is_prime = [False] * (limit + 1)
instado de:
for i in range(5,limit):
is_prime.append(False)
resolveu o problema.