Perché la mia implementazione del crivello di Atkin numeri che si affacciano vicino al limite specificato?
-
25-09-2019 - |
Domanda
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.
Soluzione
- Cambia
lim
alimit
. 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 poin==limit
sieve[n]
solleva un IndexError. Prova l'algoritmo con un valore piccolo dilimit
(ad esempio n = 50). Vedrai questo errore venire. Una soluzione semplice è quella di utilizzaresieve = [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 sullasieve
giù per uno. (Per esempio, il cambiamentosieve[n]
asieve[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 dimath.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