0

¿Alguien sabe algún un método más rápido de saber si un número grande es primo o no? Tengo el siguiente método que lo hace, pero, es lento con números muy grandes y me gustaría saber si alguien sabe otro método, sin bucle, para su comprobación. Gracias de antemano.

<!DOCTYPE html>
<head>
<html lang="es_ES" >
<meta charset="UTF-8" >
<meta name="author" content="Pol Flórez Viciana" >
<meta name="owner" content="Pol Flórez Viciana" >
<meta name="keywords" content="" >
<title>Función de Ejemplo de Número Primo</title>
<meta name="description" content="Función de ejemplo para comprobar si un número es número primo." >
<meta name="robots" content="index, dofollow" >
<style>
    h1 {
        color: blue;
    }
    h2 {
        color: green;
    }
    section {
        padding: 10px;
        width: 360px;
        min-width: 360px;
        border: solid 2px blue;
        position: absolute;
        top: 50%;
        left: 50%;
        transform: translate(-50%, -50%); 
    }
</style>
</head>
<body>
<center>
    <h1>Función es Número Primo</h1>
    <section>
        <h2>Introduzca el Número</h2>
        <input id="TextBoxInput" type="text" value="" style="width: 120px;" />
        <input id="BtnCompruebaPrimo" type="button" onclick="CompruebaNumeroPrimo()" value="Comprobar Número Primo" />
    </section>
</center>
<script>
function CompruebaNumeroPrimo(){
    var TextBoxInput = document.getElementById("TextBoxInput").value;
    var EsPrimo = esNumeroPrimo(TextBoxInput);
    alert(EsPrimo);
}
function esNumeroPrimo(Numero){
        // Método Abreviado de Comprobación de Números Primos
    var Retorno = true;
    var x = 0;
    Numero = parseFloat(Numero);
    if (Number.isInteger(Numero) == true && Numero >= 0){
        if (Numero == 0 || Numero == 1 || Numero == 4) { 
            Retorno = false; 
        }else{
            if (Numero >= 4){
                if (Numero % 2 == 0) { Retorno = false; }
                if (Retorno == true ){
                    for ( x = 3; x < Numero / 2; x = x + 2) {
                        if (Numero % x == 0) { Retorno = false; break; }
                    }
                }
            }       
        }
    }else{
        Retorno = false;
    }   
    return Retorno;
}
</script>
</body>
</html>

6
  • 1
    Tu problema no es simple. De hecho, ha ocupado al ser humano por décadas (por no decir que siglos) y se conoce como Test de Primalidad. La forma más básica (y menos eficiente) es ir testeando el numero si es divisible por todos los números menores que él. Una mejora es ir testeando si es divisible por los números impares menores que la raiz cuadrada del número en cuestión. Para números muy grandes se deben usar otros algoritmos.
    – aeportugal
    Commented el 27 oct. a las 21:32
  • Yo creo que esta pregunta no es nueva. Tal vez no no la hayan hecho en javascript pero la implementación no cambia mucho.
    – Mateo
    Commented el 27 oct. a las 22:50
  • Hasta que no se resuelva la hipótesis de Riemann dudo que haya un algoritmo más óptimo
    – Mateo
    Commented el 27 oct. a las 23:03
  • No voy a darte una respuesta directa porque esta es una pregunta que aparece bastante seguido, pero con gusto te doy un enfoque útil: para saber si un número es primo, solo necesitas verificar si es divisible por números primos menores o iguales a su raíz cuadrada. Esto se debe a que si un número tiene divisores, uno de ellos siempre será menor o igual que la raíz cuadrada del número. Entonces, en lugar de saltar de 2 en 2 o de manera constante, enfócate en probar únicamente con números primos en ese rango.
    – clay
    Commented el 28 oct. a las 16:59
  • Si para los 100 primeros números naturales, solo se hace la prueba de múltiplos con números menores a 10 con impares menores a 10, puede que haya método de acortar el tiempo sin tener que testear uno a uno los impares hasta la mitad del número en cuestión. Commented el 28 oct. a las 18:45

4 respuestas 4

6

Dudo que exista un algoritmo sin bucle para determinar si un número es primo o no. Sería el santo grial para la desencriptación.

Tú tienes un algoritmo bastante optimizado, por ejemplo:

if (Numero % 2 == 0)  //antes

Con esto descartas todos los pares, pero también podrías descartar los divisibles de 3 porque son aproximadamente un tercio de los números restantes:

if (Numero % 2 == 0 || Numero % 3) //después

Luego tienes el for

for ( x = 3; x < Numero / 2; x = x + 2) //antes

Recorres la mitad de los números, pero hay una regla de la raíz cuadrada (ver la sección de Usos y casos), que dice que debes buscar hasta la raíz cuadrada de "Numero" (bastante menos que la mitad)

Luego tu comienzas en x=3, pero si es divisible por 3 ya lo comprobamos y el 4 ya sabemos que no es primos, entonces comenzamos de x=5.

const raiz = Math.sqrt(Numero);
for (let x = 5; x <= raiz ; .....) //después

Luego tenemos que todo número primo mayor que 3 puede escribirse como 6n±1, es decir debemos comprobar: 6n-1 y 6n+1, para esto nuestro for debe quedar

const raiz = Math.sqrt(Numero);
for (let x = 5; x <= raiz ; x+=6)

Aquí x toma los siguientes valores

  • 5 -> 6*1 - 1
  • 11 -> 6*2 - 1
  • 17 -> 6*3 - 1
  • etc

Entonces tenemos que comprobar

const raiz = Math.sqrt(Numero);
for (let x = 5; x <= raiz ; x+=6){
  if( Numero % x === 0) return false; // no es primo

Pero aun nos falta comprobar cuando tiene la forma 6n+1. Lo cual es muy sencillo, si sabemos que x en cada loop toma la forma de 6n-1 para que sea 6n+1 solo debemos sumar 2 a x, quedando como:

const raiz = Math.sqrt(Numero); 
for (let x = 5; x <= raiz; x+=6){
  if( Numero % x === 0 || Numero % (x + 2) === 0) return true; //es primo

Con esto verificamos 2 números por loop.

Código completo:

function esNumeroPrimo(Numero) {
  if (Numero <= 1) return false; // Los números menores o iguales a 1 no son primos
  if (Numero <= 3) return true; // 2 y 3 son números primos
  if (Numero % 2 === 0 || Numero % 3 === 0) return false; // Elimina múltiplos de 2 y 3
  const raiz = Math.sqrt(Numero);
  for (let x = 5; x <= raiz; x += 6) {
    if (Numero % x === 0 || Numero % (x + 2) === 0) return false;
  }
  return true;
}

console.log(7, "es primo ", esNumeroPrimo(7))
console.log(6, "es primo ", esNumeroPrimo(6))
console.log(2132130, "es primo ", esNumeroPrimo(2132130))
console.log(997 , "es primo ", esNumeroPrimo(997))
console.log(64523417, "es primo ", esNumeroPrimo(64523417))

2
  • Estás calculando x * x cada iteración cuando podrías comparar x con la raíz cuadrada del número. La raíz cuadrada del número es una constante así que puedes ponerla en una variable y ahorrar más cálculos.
    – Mateo
    Commented el 27 oct. a las 22:54
  • @Mateo Toda la razón, y por las dudas lo saqué fuera del for
    – Yussef
    Commented el 27 oct. a las 23:35
0

En C++ lo haríamos de la siguiente manera, pienso que te será sencillo pasarlo a javascript. El programa comprueba si el número es divisible por los números que le preceden y el mismo, por lógica va a ser divisible por dos números, el propio número y el 1, y devuelve true si k == 2 (sólo es divisible por esos dos números) y false en cualquier otro caso (es divisible por más números). La variable k solo se incrementa en caso de ser divisible (el resto de la división es igual a cero).

bool esPrimo(int numero)
{
    int k = 0;
    for(int i = 1; i <= numero; i++)
        if (numero % i == 0)
            k++;

    return k == 2;
}
3
  • Gracias por responder. A tu función en C++ le falta la optimización en el bucle preguntando solo por los impares en vez de preguntar por uno a uno. En mi función optimice el tiempo preguntando primero si era par con la excepción del 2 y luego pregunto por todos los impares. Esto reduce el tiempo a la mitad pero sigue tardando el método. Commented el 27 oct. a las 18:18
  • Tu pregunta esta mal hecha entonces Pol, no quieres saber como hacerlo, sino como optimizarlo.
    – Excorpion
    Commented el 27 oct. a las 18:46
  • Es cierto que es un algoritmo que puede replicarse en cualquier lenguaje pero la pregunta es de Javascript
    – Mateo
    Commented el 27 oct. a las 22:58
0

Pues una simpleza lo dicho antes. Si el Número dividido entre 2 lo divides a 10 cuando el número es mayor a 100 pasa que va bastante más rápido ( sin cronometrar ) en apariencia así va más rápido:

<!DOCTYPE html>
<head>
<html lang="es_ES" >
<meta charset="UTF-8" >
<meta name="author" content="Pol Flórez Viciana" >
<meta name="owner" content="Pol Flórez Viciana" >
<meta name="keywords" content="" >
<title>Función de Ejemplo de Número Primo Optima de Pol</title>
<meta name="description" content="Función de ejemplo para comprobar si un número es número primo." >
<meta name="robots" content="index, dofollow" >
<style>
    h1 {
        color: blue;
    }
    h2 {
        color: green;
    }
    section {
        padding: 10px;
        width: 360px;
        min-width: 360px;
        border: solid 2px blue;
        position: absolute;
        top: 50%;
        left: 50%;
        transform: translate(-50%, -50%); 
    }
</style>
</head>
<body>
<center>
    <h1>Función es Número Primo Optimizada por Pol</h1>
    <section>
        <h2>Introduzca el Número</h2>
        <input id="TextBoxInput" type="text" value="" style="width: 120px;" />
        <input id="BtnCompruebaPrimo" type="button" onclick="CompruebaNumeroPrimo()" value="Comprobar Número Primo" />
    </section>
</center>
<script>
function CompruebaNumeroPrimo(){
    var TextBoxInput = document.getElementById("TextBoxInput").value;
    var EsPrimo = esNumeroPrimo(TextBoxInput);
    alert(EsPrimo);
}
function esNumeroPrimo(Numero){
        // Método Abreviado de Comprobación de Números Primos
    var Retorno = true;
    var x = 0;
    Numero = parseFloat(Numero);
    if (Number.isInteger(Numero) == true && Numero >= 0){
        if (Numero == 0 || Numero == 1 || Numero == 4) { 
            Retorno = false; 
        }else{
            if (Numero >= 4){
                if (Numero % 2 == 0) { Retorno = false; }
                if (Retorno == true ){
                    var LongitudEntero = "" + Numero;
                    if (LongitudEntero.length >= 3) {
                        for ( x = 3; x < Numero / 10; x = x + 2) {
                            if (Numero % x == 0) { Retorno = false; break; }
                        }
                    }else{
                        for ( x = 3; x < Numero / 2; x = x + 2) {
                            if (Numero % x == 0) { Retorno = false; break; }
                        }
                    }   
                }
            }       
        }
    }else{
        Retorno = false;
    }   
    return Retorno;
}
</script>
</body>
</html>

0

El código que pasó tiene algunos problemas en la validación de entrada, en el uso de Numero / 2 para verificar si es primo, y en el uso de var.

El uso de var puede causar problemas de alcance; lo más indicado es usar const o let para el control de alcance.

var Retorno = true;
var x = 0;

No incluyó la verificación de si la conversión parseFloat resulta en un número válido:

Numero = parseFloat(Numero);
if (Number.isInteger(Numero) == true && Numero >= 0) {

Y al utilizar Numero / 2 para verificar si es primo:

for (x = 3; x < Numero / 2; x = x + 2) {

Un ejemplo simple:

document.getElementById( "BtnCompruebaPrimo" ).onclick = function() {
    const numero = parseInt( document.getElementById( 'TextBoxInput' ).value );    
    if( !isNaN( numero )) {
        const esPrimo = comprobarPrimo( numero );

        if( esPrimo ) {
            alert( `Número primo: ${ numero }`);
        } 
         else {
            alert( `El número no es primo: ${ numero }`);
        }
    } 
    else {
        alert( 'Por favor, ingrese un número válido.' );
    }
};

function comprobarPrimo( numero ) {
    let primo = true;    
    if( numero < 2 ) {
        primo = false;
    }
    else {
        function esPrimoRecursivo( divisor ) {
            if( divisor * divisor > numero  ) {
                return true;
            }
            if( numero % divisor === 0 ) {
                primo = false;
                return false;
            }
            return esPrimoRecursivo( divisor + 1 );
        }
        esPrimoRecursivo( 2 );
    }
    return primo;
}
<section>
        <h2>Introduzca el Número</h2>
        <input id="TextBoxInput" type="text" value="" style="width: 120px;" />
        <input id="BtnCompruebaPrimo" type="button" value="Comprobar Número Primo" />
    </section>

La función comprobarPrimo verifica si un número es primo. Si el número es menor que 2, informará que no es primo. Para números mayores, se utilizó la función recursiva esPrimoRecursivo, que prueba si el número puede ser dividido por 2 y otros números, llamándose a sí misma hasta encontrar un divisor y confirmar que es un número primo.

En la función esPrimoRecursivo(2), porque 2 es el primer número primo. esPrimoRecursivo(divisor + 1). divisor + 1 es para probar el siguiente número, aumentando uno a la vez hasta encontrar un divisor.

2
  • La variable primo sirve solo como una referencia de control temporal para el resultado del cálculo del número primo dentro de la función recursiva. ¿De dónde saqué la respuesta? ¡Es una actividad simple que aparece en hackerrank.com como un desafío de programación y es un ejercicio que ya resolví en la universidad!...... También podría usar RxJS para resolver sin utilizar "loops" Commented el 29 oct. a las 13:37
  • Maestro, mil disculpas, la incorrecta identación sumada a mi natural tontera, colaboraron para que no viese el último return, procedo a borrar mi comentario. Commented el 29 oct. a las 16:57

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.