Si ha pasado algún tiempo en guerras de códigos, encontrar si un número es primo es un tema común entre una categoría de problemas. Cuando empecé a codificar, pensé que recorrer todos los números del 1 al num y verificar si era divisible era un gran enfoque. Sin embargo, tan pronto como me enteré de la notación big O, ¡me mortificé!

Después de un poco de investigación y lectura wiki este fin de semana, encontré una gran función para encontrar si un número es primo con un tiempo O(n) sub-lineal. La siguiente función es la solución que encontré:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. Comprueba si el número es 0, 1 o negativo. Devolver true si el número está dentro de este rango.
  2. Comprueba si el número es 2 o 3. Devolver true si el número es 2 o 3.
  3. La última instrucción if devuelve que el número no es primo si es divisible por 2 o 3.
  4. La última parte de esta función es la más complicada: ¡el bucle while! Se trata esencialmente de comprobar cada número impar que no es divisible por 3 hasta que se vuelve más grande que la raíz cuadrada del número. Por ejemplo, los primeros i y i + 2 serán 5 y 7. Los siguientes i y i + 2 serán 11 y 13. No marca 9 o 15 porque ambos son divisibles por 3 y habrían quedado atrapados en la última declaración else if.
  5. Finalmente devuelve true si el número no era divisible por ninguna entrada i o i+2 porque el número es primo.

O(n)

Si asumimos que n es el número pasado a isPrime, el O(n) de mi enfoque inicial sería O (n). Por lo tanto, esta complejidad temporal sería lineal. Esto está bien si todo lo que está haciendo es comprobar, pero muchas veces esta función es una función auxiliar y comprobar si una lista de números es primo sería exponencial.

La función anterior isPrime sería O (n^1/2). Esto significa que la complejidad de tiempo será sub-lineal, lo que disminuirá en gran medida la complejidad de tiempo de una función más grande.

En Conclusión