La respuesta literal es imprimir “infinito” ya que hay un número infinito de números primos. Sin embargo, supongo que te refieres al número de primos menor o igual que algún número de entrada n.
Lo mejor en términos de uso sencillo sería utilizar algún software existente:
- Python / SymPy primepi
- Pari / GP primepi
- Wolfram Alpha Pi [n]
- Perl / ntheory prime_count
- primer conde
Los tres últimos utilizan métodos de vanguardia, y el último es, en computadoras paralelas, con mucho, el más rápido. También es el único práctico para entradas de más de 64 bits. Los dos últimos también tienen buenas aproximaciones y límites disponibles.
- ¿Cuál es el algoritmo perfecto para extraer la forma, el color, la textura y los bordes de las partes cilíndricas en MATLAB en preparación para el aprendizaje supervisado?
- ¿Hay alguna guía sobre el uso de datos sintéticos para entrenar algoritmos de visión por computadora? ¿Hay alguna investigación al respecto?
- ¿Cuáles son los algoritmos de búsqueda paralelos más importantes? ¿Qué ventajas tienen sobre los algoritmos de búsqueda clásicos?
- ¿Cómo se soluciona el problema de Little Red-Cap (TAP2013C) en SPOJ?
- ¿Cuál: Estructura de datos y pensamiento algorítmico con Python (Narasimha Karumanchi) o Estructuras de datos y algoritmos en Python (Michael T. Goodrich)?
Lo mejor en términos de fácil programación sería el Tamiz de Eratóstenes. Simplemente criba hasta tu número n y cuenta el número de números primos. Esto está bien para números pequeños, pero muy pronto comienza a usar memoria excesiva y necesita pasar a un tamiz segmentado (que también aumenta el rendimiento). Pero incluso eso se agota y se vuelve bastante lento. Se puede debatir si el método de división de prueba más lento (como se muestra en la respuesta de Gipma) es más fácil de programar, pero un SoE implementado correctamente es solo de 4 líneas de código (ver Wikipedia), así que creo que no está bien definido. El SoE será mucho más rápido a medida que aumente el tamaño de entrada. Los métodos de conteo rápido primario son órdenes de magnitud más rápidos que el tamizado y la única respuesta práctica para entradas de más de, por ejemplo, 10 ^ 11 (depende de su tolerancia para las horas de espera frente a los segundos). Para insumos pequeños, como menos de unos pocos millones, una división de tamiz o de prueba debería ser completamente adecuada para la mayoría de los propósitos.
Lo mejor en términos de eficiencia algorítmica sería el método LMO extendido (las mejoras de Deléglise y Rivat al método LMO de Lagarias, Miller y Odlyzko) o el método analítico de Lagarias y Odlyzko (primero analizado por Riesel y Göhl, creo, mejorado por Galway e implementado por Franke et al. y Platt). Los métodos combinatorios (incluido el OVM) son prácticamente programables por muchas personas: vinculé a dos implementaciones de código abierto anteriores y hay más. El libro de Riesel de 1994 describe los algoritmos anteriores de Meissel, Legendre y Lehmer de una manera muy comprensible. Los métodos analíticos no son del todo fáciles de entender ni de programar correctamente; los han realizado instituciones de investigación o como trabajo académico serio.
Los últimos registros se han establecido utilizando el programa de cuenta abierta de código abierto de Kim Walisch, que utiliza el método Deléglise-Rivat. Teniendo en cuenta que esto implica no solo un algoritmo rápido y una implementación eficiente, sino también un soporte de 128 bits y un gran esfuerzo en la paralelización eficiente en clústeres.
