Funkcja liczenia pierwiastków pi (x) oblicza liczbę liczb pierwszych nieprzekraczającą x i od stuleci fascynuje matematyków. Na początku XVIII wieku Adrien-Marie Legendre podał wzór za pomocą funkcji pomocniczej phi (x, a), która zlicza liczby nie większe niż x, które nie są dotknięte przesiewaniem pierwszych liczb pierwszych; na przykład, phi (50,3) = 14 dla liczb 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 i 49. Funkcję phi można obliczyć jako phi (x, a) = phi (x, a-1) - phi (x/P (a), a-1), gdzie phi (x, 1) to liczba nieparzystych liczb całkowitych nieprzekraczająca x i P (a) jest a-tą liczbą pierwszą (licząc od 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
Tablica p przechowuje a-prim dla małych a, obliczanych przez przesiewanie. Pamięć podręczna jest ważna; bez niego czas pracy byłby wykładniczy. Biorąc pod uwagę phi, podstawową formułą obliczeniową Legendre'a jest pi (x) = phi (x, a) + a - 1, gdzie a = pi (floor (sqrt (x))). Legendre użył swojej formuły do obliczenia pi (10^6), ale zgłosił 78526 zamiast poprawnej odpowiedzi 78498, która, mimo że błędna, była zadziwiająco bliska skomplikowanego ręcznego obliczenia.
W 1950 Derrick H. Lehmer dało ulepszony algorytm do zliczania liczby pierwsze:
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
Na przykład, PI (10^12) = 37607912018. Mimo tych algorytmów, oraz ich współczesnych odmian i bardzo szybkich komputerach, jest ogromnie żmudne obliczanie dużych wartości pi; pi (10^24) = 18435599767349200867866.
Aby użyć tego algorytmu do obliczenia n-tej liczby pierwszej, następstwo twierdzenia o liczbie pierwszej ogranicza n-ty prime P (n) pomiędzy n log n i n (log n + log log n) dla n> 5, więc obliczyć pi na granicach i użyć bisekcji, aby określić n-ty wstęp, przestawić się na przesiewanie, gdy granice są blisko.
Omawiam liczby pierwsze w kilku pozycjach na my blog.
Przepraszam, to nie jest McDonalds - nie masz tutaj próśb. Masz pytania. Dokładne problemy z programowaniem ... Przeczytaj [FAQ] – ppeterka
, jeśli nie jest prawdą, że 'floor (x/j) * j == x - (x% j)'. Następnie formuła, do której linkujesz, staje się 'pi (x) = (-1) + SUMA {j = 3..n} (((j-2)!)% J)' (?). Następnie użyj mnożenia modułowego (tj. '5!% 7 == (((((2 * 3)% 7) * 4)% 7) * 5)% 7'). –
@SeverynKozak Powodem, dla którego mówią, że to nie jest pytanie o programowanie, jest to, że twoje pytanie nie zawiera kodu. –