Por que minha implementação da peneira de Atkin está com vista para os números próximos ao limite especificado?

Question

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.

Answer 1

• Mudar lim para limit. 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. Se n==limit então sieve[n] Aumenta um IndexError. Experimente o seu algoritmo com um pequeno valor de limit (por exemplo, n = 50). Você verá esse erro surgir. Uma correção fácil é usar

  sieve = [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 índice sieve para baixo por um. (Por exemplo, mudança sieve[n] para sieve[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 do math.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