Perché la mia implementazione del crivello di Atkin numeri che si affacciano vicino al limite specificato?

Question

La mia implementazione di Crivello di Atkin sia affaccia numeri primi vicini al limite o compositi vicino al limite . mentre alcuni limiti funzionano e altri no. Sto sono completamente confuso da ciò che è sbagliato.

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

Per esempio, quando ho generare un numeri primi al limite del 1000, l'Atkin vaglio manca il primo 997, ma include il composito 965. Ma se io generare fino al limite del 5000, l'elenco viene restituito è del tutto corretto.

Answer 1

• Cambia lim a limit. Naturalmente si doveva sapere che.
• Dal sieve = [False]*limit, L'indice più grande consentito è limit-1.

  Tuttavia, su questa linea

  if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
  

  si sta verificando se n<=limit. Se poi n==limit sieve[n] solleva un IndexError. Prova l'algoritmo con un valore piccolo di limit (ad esempio n = 50). Vedrai questo errore venire. Una soluzione semplice è quella di utilizzare

  sieve = [False]*(limit+1)
  

  La soluzione semplice è un po 'uno spreco dal setaccio [0] non viene mai utilizzato. Così si potrebbe pensare una correzione migliore è quello di mantenere sieve = [False]*limit, ma risolvere tutto il vostro altro codice facendo un passo l'indice sulla sieve giù per uno. (Per esempio, il cambiamento sieve[n] a sieve[n-1] ovunque, ecc) Tuttavia, questo vi costringerà a fare un certo numero di sottrazioni extra che non sarà buono per la velocità. Quindi la soluzione facile / spreco in realtà è probabilmente l'opzione migliore.

• http: //en.wikipedia. org / wiki / Sieve_of_Atkin , x deve essere un numero intero in [1, sqrt (limite)], comprensivo dei punti finali.

  Nel codice

  factor = int(math.sqrt(limit))
  

  e int prende il piano di math.sqrt(limit). Inoltre,

  range(1,factor) va da 1 a fattore-1. Così si è fuori di 1.

  Quindi, è necessario modificare questo per

  factor = int(math.sqrt(limit))+1
  

• Vedere modo più veloce per elencare tutti i primi sotto N per un'alternativa (e più veloce) attuazione del crivello di Atkin, a causa di 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