isPrime en JavaScript

1. Solución ingenua para verificar si un número es primo en JavaScript
2. Solución de raíz cuadrada para verificar si un número es primo en JavaScript

Un número primo es mayor que uno con dos factores: uno y él mismo. Significa que los números primos siempre dejan un resto cuando se dividen por otros números. Los otros números mayores que uno con más de dos factores se llaman números compuestos.

Este artículo discutirá diferentes métodos para verificar si un número es primo en JavaScript.

Solución ingenua para verificar si un número es primo en JavaScript

La forma más fácil de verificar si un número n es primo es iterar de 2 a n-1 y luego verificar si n es divisible por cada uno de ellos.

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= n - 1; i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

Complejidad del tiempo

Iteramos n-2 veces de 2 a n-1. La complejidad temporal de esta solución es O(n).

Complejidad espacial

La complejidad espacial de esta solución es O(1).

Solución de raíz cuadrada para verificar si un número es primo en JavaScript

La solución anterior puede mejorar iterando solo hasta sqrt(n). Se basa en el hecho de que sqrt(n) * sqrt(n) = n, y tiene que haber al menos un factor menor que igual a sqrt(n). Si no podemos encontrar ningún factor en el rango de [2, sqrt(n)], significa que el número n es un número primo.

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= Math.sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

Complejidad del tiempo

Dado que iteramos los primeros factores potenciales sqrt(n), la complejidad temporal de la solución anterior es sqrt(n).

Complejidad espacial

La complejidad espacial de esta solución es O(1).