Algoritmo veloce per trovare il numero di numeri primi tra due numeri

Question

Il mio problema si riduce alla ricerca del numero di numeri primi tra due numeri dati. Potrei avere un intervallo grande come 1 to (1000)! e quindi ho bisogno di alcune ottimizzazioni matematiche.

Chiaramente il metodo di setacciare sarebbe troppo lento in questo caso. C'è qualche ottimizzazione matematica che può essere applicata - come ad esempio, prendendo un sottoinsieme più piccolo di questo grande spazio e facendo inferenze sul resto dei numeri.

P.S: Sembra davvero che potrei aver raggiunto un punto morto, ma tutto quello che sto cercando sono alcune ottimizzazioni che potrebbero aiutare a risolvere questo. E inoltre, sto solo cercando un approccio a thread singolo.

EDIT: Un approccio che ho pensato e in grado di risolvere un sacco di grandi problemi relativi ai numeri primi - è che qualcuno mantenga una tabella globale di numeri primi e la renda disponibile per la ricerca. La gente del progetto PrimeGrid può contribuire utilmente a questo.

Answer 1

Dal momento che si desidera andare fino a 1000! (fattoriale). Non sarai in grado di ottenere risultati esatti con i metodi attualmente conosciuti sulla tecnologia attuale.

Il Prime Counting Function è stato valutato solo esattamente per una manciata di valori fino a 10^24. Quindi in nessun modo sarete in grado di colpire 1000!.

---

Ma dal momento che si parla di un'approssimazione può andare bene, è possibile utilizzare il Logarithmic Integral come approssimazione per la funzione di conteggio Prime.

Questo si basa sul Prime Number Theorem che dice che il Primo funzione conteggio è asintotica alla logaritmica integrale.

Answer 2

Il metodo più veloce che conosco sarebbe quello di eliminare tutti i noti non primi (numeri pari, tutti i numeri con divisori inferiori al numero iniziale nell'intervallo, ecc.) Il più velocemente possibile, quindi scorrere su il resto e usa qualcosa come lo Euclidean algorithm per determinare se quel numero è un numero primo.

Answer 3

È possibile esaminare le opzioni qui: http://en.wikipedia.org/wiki/Prime_counting_function

Questo sembra anche utile: http://mathworld.wolfram.com/PrimeCountingFunction.html

Posso chiederle perché ne hai bisogno fino a 1000! ? Sembra che nessuno abbia mai contato così tanti prima. Ci sono 1.925.320,391,606,803,968,923 numeri primi da 1 a 10^23. 1000! = 10^120. Sono curioso ora.

Answer 4

C'è un fast, simple approximation per il numero di numeri primi di un dato limite. Se non hai bisogno di valori esatti, una differenza tra due valutazioni di questa formula ti farà avvicinare.

Answer 5

L'algoritmo di conteggio primo sviluppato da Lagarias e altri, citato da altri, funziona molto approssimativamente in O (n^(2/3)). Dal momento che un setaccio per i numeri primi da k1 a k2 richiede all'incirca O (max (sqrt (k2), k2 - k1), dovresti controllare quanto distano i limiti inferiore e superiore e fare un setaccio o usare l'algoritmo di conteggio dei primi , qualunque sia più veloce

BTW: l'algoritmo di conteggio dei primi può essere regolato per contare i numeri primi da 1 a n per vari valori n ragionevolmente vicini tra loro più rapidi del conteggio individuale.(Fondamentalmente, sceglie un numero N, crea un setaccio di dimensione n/N e cerca i valori N^2 in quel setaccio.La O (n^(2/3)) deriva dal fatto che per N = n^(1/3) entrambe le operazioni richiedono N^(2/3) passi.Questo setaccio può essere riutilizzato per diversi n, ma devono essere cercati valori diversi Quindi per k valori diversi di n, si rende N un po 'più piccolo, aumentando il costo del setaccio (solo una volta) ma riducendo il costo della ricerca (k volte)).

Per n circa 1000 !, non c'è alcuna possibilità. Non puoi nemmeno contare il numero di numeri primi in [n, n] per valori di quella dimensione se n non ha fattori (ish) piccoli.