Come posso utilizzare il setaccio di Eratostene per ottenere l'ennesimo numero primo?

Question

Ho scritto una funzione, sieve(n), che utilizza il setaccio di Eratostene per restituire una matrice di tutti i numeri primi fino a n.

sieve(25) # ==> [2, 3, 5, 7, 11, 13, 17, 19, 23] 

La fonte per questa funzione può essere letto here.

Voglio refactoring questo ora in modo che sieve(n) restituirà il primo n. Non sono sicuro di come lo farei. Non voglio scrivere una funzione completamente nuova e più elaborata, quindi sembra che il metodo migliore sia capire a quale valore il setaccio dovrebbe contare.

Ad esempio, se chiedo il 27 ° primo, l'elenco iniziale di setacci dell'intervallo deve essere compreso tra 2 e (qualcosa che so che il 27 ° primo non è maggiore di). Ma c'è un modo semplice per capire qual è questo valore?

Ho ricercato questa domanda e trovarono this Quora post cui detto che il primo all'ennesimo deve essere compreso tra n*Math.log(n) + n*(Math.log(Math.log(n))-1) e n*Math.log(n) + n*Math.log(Math.log(n)) (dove Math.log rubino per il logaritmo naturale), ma semplicemente facendo list una matrice di numeri tra queste due figure rende la resa setaccio valori strani, come 56 per il 15 ° primo (56 non è primo e la risposta dovrebbe essere 47).

Come potete immaginare, sono totalmente fuori dal mio elemento qui. Se qualcuno potesse offrirmi qualche consiglio lo apprezzerei davvero.

Answer 1

Il setaccio di Eratostene deve sempre iniziare dall'inizio; non puoi setacciare in un intervallo arbitrario poiché perdi tutti i numeri primi più piccoli. Quindi non devi preoccuparti di un limite inferiore, solo per un limite superiore. Che ti ha dato, e che Wikipedia conferma che:

p _n < n ln ( n ln n) per n ≥ 6

Così semplicemente prendere quel limite, la spina nel tuo n e continua fino a quando non hai trovato n numeri primi. Il tuo setaccio di solito sarà un po 'troppo grande, ma non troppo se il limite è ragionevolmente stretto, cosa che penso sia il caso.

Vedere here per una tabella di tale limite o here per un grafico. A proposito, il codice che crea la tabella sta facendo la stessa cosa. Volevo almeno 500 voci, così ho calcolata

n = 500 
lst = list(range(2, ceil(n*log(n*log(n))))) 
ps = [] 
while lst: 
    p = lst[0] # next prime 
    ps.append(p) 
    lst = [i for i in lst if i % p != 0] 

e ottenuto un po 'più di 500 numeri primi fuori di esso, per il quale ho poi potuto vedere come la calcolata legati confronta al valore reale.