Verificar si un número es primo - rápido
Hasta ahora, para determinar si un número
n es primo o no, se utilizaba básicamente una búsqueda lineal de divisores. Esto significa que, al aumentar n, la cantidad de operaciones necesarias para averiguar si n es primo o no crece de forma proporcional (con alguna constante multiplicada). Así, considerando los peores casos (todas las ocasiones en las que n era un número primo —51, 107, etcétera—), nuestro algoritmo realizaba aproximadamente n/4 operaciones para comprobar la primalidad de n.Esto implica que al multiplicar
n por 10, el algoritmo llevaría a cabo 10 veces más operaciones. Si multiplicamos n por 100, realizaría 100 veces más operaciones. En otras palabras, nuestro algoritmo funciona de manera proporcional a n. ¿Hay alguna forma de hacerlo más rápido? Parece que todavía hay muchos chequeos redundantes.El enfoque de :
Imaginemos que el número
n tiene un divisor d.Esto significa que
n es divisible por d y tanto d como son números enteros. Además, o bien d o bien es menor o igual que . Por lo tanto, cuando comprobamos si un número es primo, podemos iterar hasta llegar a en lugar de . Nos interesa verificar si un número es divisible por algún número distinto de 1 y del propio n, así que podemos fijarnos en el menor entre d y . En consecuencia, dado que uno u otro será menor que , basta con recorrer hasta y detener el bucle ahí.¡Este es un gran avance! Realizar operaciones en lugar de
n marca una diferencia enorme. Imaginemos un algoritmo que necesita 10 años (3650 días) para completar un cálculo. Si lo optimizamos para usar operaciones en lugar de n, sólo necesitaría 2 meses (61 días) para terminar.¿Existen algoritmos mejores para comprobar la primalidad de un número?
¡Sí! Puedes leer más sobre ellos en Algorithms for Competitive Programming. Hay algoritmos cuyo crecimiento (en número de operaciones conforme
n aumenta) es logarítmico en lugar de .Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ ).Salida
El programa debe imprimir
Yes si n es primo y No en caso contrario.Ejemplos
Entrada | Salida |
1 | No |
11 | Yes |
353557 | Yes |
34134741 | No |
902468477 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB