La funzione di conteggio primo pi (x) calcola il numero di numeri primi non superiori a x e ha affascinato i matematici per secoli. All'inizio del diciottesimo secolo, Adrien-Marie Legendre diede una formula usando una funzione ausiliare phi (x, a) che conta i numeri non superiori a x che non vengono colpiti setacciando con il primo un primes; per esempio, phi (50,3) = 14 per i numeri 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 e 49. La funzione phi può essere calcolata come phi (x, a) = phi (x, a-1) - phi (x/P (a), a-1), dove phi (x, 1) è il numero di interi dispari che non superano x e P (a) è l'a-esimo numero primo (contando da P (1) = 2).
function phi(x, a)
if (phi(x, a) is in cache)
return phi(x, a) from cache
if (a == 1)
return (x + 1) // 2
t := phi(x, a-1) - phi(x // p[a], a-1)
insert phi(x, a) = t in cache
return t
Una matrice p memorizza l'a-esima per a a, calcolata da setacciatura. La cache è importante; senza di esso, il tempo di esecuzione sarebbe esponenziale. Dato phi, la formula di conteggio primi di Legendre è pi (x) = phi (x, a) + a - 1, dove a = pi (floor (sqrt (x))). Legendre ha usato la sua formula per calcolare pi (10^6), ma ha segnalato 78526 invece della risposta corretta di 78498, che, anche se errata, era sorprendentemente vicina per un complicato calcolo manuale.
Nel 1950, Derrick H. Lehmer dato un algoritmo migliorato per i numeri primi conteggio:
function pi(x)
if (x < limit) return count(primes(x))
a := pi(root(x, 4)) # fourth root of x
b := pi(root(x, 2)) # square root of x
c := pi(root(x, 3)) # cube root of x
sum := phi(x,a) + (b+a-2) * (b-a+1)/2
for i from a+1 to b
w := n/p[i]
lim := pi(sqrt(w))
sum := sum - pi(w)
if (i <= c)
for j from i to lim
sum := sum - pi(w/p[j]) + j - 1
return sum
Ad esempio, tav (10^12) = 37607912018. Anche con questi algoritmi e loro varianti moderne, e computer molto veloci, rimane terribilmente noioso calcolare valori elevati di pi; al momento della stesura, il più grande valore noto è pi (10^24) = 18435599767349200867866.
Per utilizzare questo algoritmo per calcolare l'n-esimo, un corollario al Teorema numero primo limita l'n-esimo P (n) tra n log n e n (log n + log log n) per n> 5, quindi calcola pi ai limiti e usa bisezione per determinare l'n-esimo, passando alla setacciatura quando i limiti sono vicini.
Discuto di numeri primi in più voci allo my blog.
Siamo spiacenti, questo non è McDonalds - non hai richieste qui. Hai domande. Informazioni su problemi di programmazione esatti ... Si prega di leggere la [FAQ] – ppeterka
se è vero che 'floor (x/j) * j == x - (x% j)'. Quindi la formula che si collega diventa 'pi (x) = (-1) + SUM {j = 3..}} (((j-2)!)% J)' (?). Quindi usa la moltiplicazione modulare (ad esempio '5!% 7 == (((((2 * 3)% 7) * 4)% 7) * 5)% 7'). –
@SeverynKozak La ragione per cui dicono che non si tratta di una questione di programmazione è perché la tua domanda non contiene codice. –