Verificar si un número es primo – un poco más rápido
Supongamos que tenemos un programa que determina si un número es primo y que ya se está utilizando en la producción de una gran empresa. Sin embargo, a medida que la compañía crece rápidamente y el número de usuarios aumenta, también lo hace la cantidad de solicitudes que llegan a tu código. Te piden que lo optimices y lo hagas un poco más veloz para que la empresa pueda manejar la avalancha de nuevos usuarios de manera eficiente.
Tu solución anterior probablemente consistía en:
- Recorrer los números desde 2 hasta
ny contar el número de divisores.
- Recorrer los números desde 2 hasta
ny detenerse en cuanto se encontrara un divisor.
Existen varios pequeños ajustes que podemos aplicar para optimizar la ejecución:
Optimización 1:
En lugar de revisar todos los números desde 2 hasta
n, podemos verificar si n es divisible por 2 y luego solo comprobar los números impares. Si el número no es divisible por 2, no hay necesidad de revisar ninguno de los números pares más grandes (4, 6, 8, 10, 12, etc.).Optimización 2:
En lugar de recorrer desde 2 hasta
n, podemos recorrer hasta n/2, ya que el divisor más pequeño posible es 2 ⇒ no encontraremos divisores mayores que n/2.Podemos combinar las optimizaciones 1 y 2. Así, los únicos candidatos serían los números impares hasta
n/2. Habría aproximadamente n/4 números que revisar, por lo que esta optimización hace que el código sea 4 veces más eficiente que hacer una búsqueda lineal simple.Estas optimizaciones harán que el código sea un poco más rápido, pero en términos de complejidad, el algoritmo sigue haciendo una búsqueda lineal de divisores. Por lo tanto, a medida que
n aumenta, el algoritmo realizará proporcionalmente más operaciones. Más adelante veremos cómo optimizar drásticamente la verificación de primalidad para que no realice más trabajo conforme n se hace más grande.Entrada
La primera línea de la entrada contiene un único entero
n (1 ≤ n ≤ ).Salida
El programa debe imprimir
Yes si n es primo y No en caso contrario.Ejemplos
Entrada | Salida |
8 | No |
7 | Yes |
1 | No |
19 | Yes |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB