Resuelven problemas diferentes pero relacionados. El SoE genera primos . La prueba de Miller-Rabin determina la compostura (que se puede convertir en determinar la primalidad o la primitiva probable).
Si puede amortizar algo de tiempo de inicio, tener algo de memoria y sus números no son demasiado grandes, entonces se puede ejecutar un tamiz una vez y dar respuestas rápidas a los números en su rango. Fuera del rango, solo estás haciendo una división de prueba, que es realmente lenta.
La prueba de primalidad más rápida para números de 32 bits más allá del rango pequeño (más de 500k más o menos) es una prueba de Miller-Rabin hash de base única. Es determinista y funciona mucho más rápido que la división de prueba con un tamiz. Para las entradas de 64 bits, existen bases MR deterministas que le dan una respuesta rápidamente. Tamizar aquí será dolorosamente lento en comparación. Una vez que supere los 64 bits, la división de prueba completa rápidamente se vuelve inútilmente lenta.
- ¿Cuál es el algoritmo más poderoso en el mundo de las aplicaciones?
- En Python, ¿cómo reemplazo una cadena en el texto sin reemplazar las subcadenas?
- ¿Qué tipo de trabajo haría un cosmólogo en el CERN?
- ¿Cuál es el mejor algoritmo para ocultar datos en texto?
- ¿Por qué Java utiliza una implementación mediocre de hashCode para cadenas?
Por lo tanto, para responder a su primera pregunta, es útil cuando se realizan pruebas de primalidad únicas en entradas no pequeñas. Es especialmente útil para probables pruebas primarias de entradas grandes.
En cuanto al problema de hackerrank, el problema tiene dos partes: dado un rango, filtra los números primos y filtra los números cuyos dígitos son primos. Este último tiene algunos atajos interesantes (por ejemplo, hay rangos de entrada que no pueden dar ningún resultado). Sin embargo, la primera es una aplicación de tamiz clásica: queremos generar primos en un rango razonablemente pequeño. Podemos hacerlo con bastante facilidad y bastante rápido. Luego simplemente eliminamos los resultados que tienen dígitos prohibidos.
Podrías encontrar una forma inteligente de generar los números no prohibidos en el rango, que no es un número enorme y generalmente más pequeño que el número de primos, y luego prueba la primalidad de cada uno. Es una pregunta interesante.
