Hay alguna forma o función para averiguar el número de números primos números de cualquier número? (Decir $10^7$ o $10^{30}$ o $200$ o $300$?)
Respuestas
¿Demasiados anuncios?
$$\pi(n) \approx \frac{n}{\ln(n)}$$
donde $\pi(n)$ es el número de números primos menos de $n$ $\ln(n)$ es el logaritmo natural de $n$. (Googlear 'Teorema de los números Primos' diré más! Pero esto parece particularmente agradable para una página de introducción: http://primes.utm.edu/howmany.shtml#pnt )
SLaks
Puntos
391154
Las respuestas anteriores son muy correcta y el estado el Teorema de los números Primos. Tenga en cuenta que por debajo de, $\pi(n)$ significa que los números primos menores o iguales a $n$. Pafnuty Chebyshev ha demostrado que si $$\lim_{n \to \infty} {\pi(n) \over {n \over \ln(n)}}$$exists, it is $1$. There are a lot of values that are approximately equal to $\pi(n)$ de hecho, como se muestra en la tabla.
Anthony Shaw
Puntos
858
Una de las aproximaciones más cercanas a $\pi(x)$ es el registro integral, $\mathrm{Li}(x)$. La expansión asintótica es fácil derivar usando integración por partes: $$ \begin{align} \mathrm{Li}(x) &=\int_2^n\frac{\mathrm{d}t}{\log(t)}\\ &=\frac{n}{\log(n)}+C_1+\int_2^n\frac{\mathrm{d}t}{\log(t)^2}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+C_2+\int_2^n\frac{\mathrm{2\,d}t}{\log(t)^3}\\ &=\frac{n}{\log(n)}+\frac{n}{\log(n)^2}+\frac{2n}{\log(n)^3}+C_3+\int_2^n\frac{\mathrm{3!\,d}t}{\log(t)^4}\\ &=\frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\frac2{\log(n)^2}+\dots+\frac{k!}{\log(n)^k}+O\left(\frac1{\log(n)^{k+1}}\right)\right) \end{align} $$ Por lo tanto, el uso de los dos primeros términos de la serie asintótica, $$ \begin{align} \frac{n}{\log(n)}\left(1+\frac1{\log(n)}+\dots\right) &=\frac{n}{\log(n)\left(1-\frac1{\log(n)}+\dots\right)}\\ &\approx\frac{n}{\log(n)-1} \end{align} $$ Por lo tanto, $\dfrac{n}{\log(n)-1}$ es una mejor aproximación de $\dfrac{n}{\log(n)}$ grandes $n$.
Mohan
Puntos
4149
No se conoce expicit fórmula para esto, pero sí sabemos cómo esta función se comporta asintóticamente, que es el famoso primer número teorema. Se establece que $$ \pi(n) \approx n/ln(n)$$
Pero hay ciertos algoritmos para el cálculo de esta función. Un ejemplo es aquí Computación π(x): El Meissel, Lehmer, Lagarias, Miller, Odlyzko método
