Dependerá de cuántos números primos necesite encontrar. Si puede conformarse con encontrar todos los números primos de menos de aproximadamente 2 mil millones, el Tamiz de Eratóstenes funcionaría muy bien y corre bastante rápido. Tampoco requiere ninguna matemática realmente elegante para que funcione.
Para comenzar, haga una matriz de 2 mil millones de ‘cajas’. Si intenta usar números enteros, corre el riesgo de quedarse sin memoria. Tiendo a usar un BitSet cuando está disponible, pero una matriz de caracteres también podría funcionar.
Ahora, marcaremos los ‘cuadros’ como primos o no, dependiendo del índice del cuadro. De esta manera no tenemos que almacenar los números reales, solo usaremos los índices.
- ¿Por qué sigo olvidando cómo funciona el algoritmo djikstra?
- ¿Qué son los algoritmos de clasificación y búsqueda?
- En IA, ¿los datos son más importantes que los algoritmos?
- ¿Qué temas básicos hay que saber en C ++ antes de aprender estructuras de datos y algoritmos?
- Cómo ordenar matrices en C
Desactive todas las casillas para indicar ‘no primo’.
Ignora los cuadros 0 y 1 porque no pueden ser primos.
Comience con el primer cuadro mayor que 1 sin marcar. (Eso debería llevarlo al recuadro 2) Marque como primo y marque todos los múltiplos de 2 como no primo.
Ahora, encuentre el siguiente cuadro sin marcar (cuadro 3). Márquelo como primo y marque todos los múltiplos de 3 como no primo.
Continúe de esta manera y cuando haya terminado, habrá marcado todos los números primos de menos de 2 mil millones. Una computadora puede realizar todo esto en menos de 30 segundos.
He escrito buscadores principales como este en varios lenguajes, incluidos C # y Java, y tienen un rendimiento muy similar. Tiendo a usar esto como una prueba para mi aprendizaje de un nuevo lenguaje de programación y hay sitios web que puedes usar para validar tus resultados.
