Te damos la bienvenida a nuestra página, en este sitio hallarás la solucíon a lo que estabas buscando.
Solución:
En lugar de una lista ordenada de números primos, dado el rango relativamente pequeño al que se apunta, tenga un array indexado por todos los números impares en el rango (sabe que no hay primos pares excepto el caso especial de 2) y que contiene el primo más cercano. Encontrar la solución se convierte en O(1) en el tiempo.
Creo que el número primo número 100 es alrededor de 541. un array de 270 [small] ints es todo lo que se necesita.
Este enfoque es particularmente válido, dada la relativa alta densidad de números primos (en particular en relación con los números impares), en el rango por debajo de 1.000. (Ya que esto afecta el tamaño de un árbol binario)
Si solo necesita buscar en los primeros 100 números primos, simplemente cree una tabla ordenada de esos números primos y realice una búsqueda binaria. Esto lo llevará a un número primo o a un lugar entre dos, y verificará cuál de ellos está más cerca.
Editar: dada la distribución de números primos en ese rango, probablemente podría acelerar las cosas (un poquito) usando una búsqueda de interpolación; en lugar de comenzar siempre en el medio de la tabla, use la interpolación lineal para adivinar un comienzo más preciso punto. El número primo número 100 debe estar alrededor de 250 más o menos (supongo que no lo he comprobado), por lo que si (por ejemplo) quisiera el más cercano a 50, comenzaría aproximadamente 1/5 del camino hacia los array en lugar de a la mitad. Prácticamente puedes tratar los números primos como si comenzaran en 1, así que simplemente divide el número que quieras por el más grande de tu rango para adivinar el punto de partida.
Las respuestas hasta ahora son bastante complicadas, dada la tarea en cuestión. Los primeros cien primos son todos menores de 600. Crearía un array de tamaño 600 y coloca en cada uno el valor del primo más cercano a ese número. Luego, dado un número para probar, lo redondearía hacia arriba y hacia abajo usando el floor y ceil funciones para obtener una o dos respuestas candidatas. Una simple comparación con las distancias a estos números te dará una respuesta muy rápida.
Si haces scroll puedes encontrar las reseñas de otros gestores de proyectos, tú igualmente puedes mostrar el tuyo si te gusta.