Por que minha implementação da peneira de Atkin está com vista para os números próximos ao limite especificado?
-
25-09-2019 - |
Pergunta
Minha implementação de Peneira de atkin Perlo de vista para os primos próximos ao limite ou compostos próximos ao limite. Enquanto alguns limites funcionam e outros não. Estou completamente confuso sobre o que está errado.
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 exemplo, quando eu gero primos ao limite de 1000, o Atkin Sieve perde o Prime 997, mas inclui o composto 965. Mas se eu gerar o limite de 5000, a lista que retorna será completamente correta.
Solução
- Mudar
lim
paralimit
. Claro que você deve ter sabido disso. - Desde
sieve = [False]*limit
, o maior índice permitido élimit-1
.No entanto, nesta linha
if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
você está verificando se
n<=limit
. Sen==limit
entãosieve[n]
Aumenta um IndexError. Experimente o seu algoritmo com um pequeno valor delimit
(por exemplo, n = 50). Você verá esse erro surgir. Uma correção fácil é usarsieve = [False]*(limit+1)
A correção fácil é um pouco desperdiçada, pois a peneira [0] nunca é usada. Então você pode pensar que uma correção melhor é manter
sieve = [False]*limit
, mas corrija todo o seu outro código pisando o índicesieve
para baixo por um. (Por exemplo, mudançasieve[n]
parasieve[n-1]
Em todos os lugares, etc.), no entanto, isso o forçará a fazer várias subtrações extras que não serão boas para a velocidade. Portanto, a solução fácil/desperdiçada é provavelmente a melhor opção. - De acordo com http://en.wikipedia.org/wiki/sieve_of_atkin, x deve ser um número inteiro em [1, sqrt (limite)], inclusive os pontos de extremidade.
Em seu código
factor = int(math.sqrt(limit))
e
int
leva o piso domath.sqrt(limit)
. Além disso,range(1,factor)
passa de 1 ao fator-1. Então você está desligado por 1.Então você precisa mudar isso para
factor = int(math.sqrt(limit))+1
- Ver Maneira mais rápida de listar todos os primos abaixo n Para uma implementação alternativa (e mais rápida) da peneira de Atkin, devido 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