El cálculo de números primos siempre ha sido un tema muy apasionante desde el punto de vista de la eficiencia, ya que entre algunas de las aplicaciones prácticas que requieren números primos muy grandes, se encuentra la criptografía. Uno de los algoritmos más usado en dicho campo es el algoritmo RSA.
PROBLEMA
Se desea calcular la cantidad de números primos que existen en un rango de N números enteros positivos.
SOLUCIÓN
En tu aproximación de la solución tenemos el clásico condicional para determinar si un número es primo o no lo es:
const elementos = 100;
const primos = [];
let iteraciones = 0;
for(let candidato = 2; candidato <= elementos; candidato++) {
let primo = true;
for(let divisor=2; divisor < candidato; divisor++) {
iteraciones++;
if(candidato%divisor === 0) {
primo = !primo;
break;
}
}
if(primo) primos.push(candidato);
}
console.log(`iteraciones: ${iteraciones}`);
console.log(primos);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Este algoritmo puede ser más eficiente. Si analizamos la parte en la que dividimos el candidato por el divisor, estamos haciendo una serie de divisiones adicionales innecesarias. Para este caso, con un valor de N=100 tenemos un total de 1133 iteraciones!!!
Explicación
Un número compuesto n, es cualquier número natural no primo, que puede ser escrito de la forma:
n = a * b; { con a y b distintos de 1 y además si a >= b entonces b <= sqrt(n) y viceversa}
Esto significa que tanto a, como b (divisores de n) tienen un valor máximo que depende uno del otro.
Entonces, no es necesario iterar todos los valores desde 2 hasta n buscando los posibles divisores de n, basta con iterar hasta la raíz cuadrada de n. Y como la misma no será exacta en la mayoría de los casos, podemos prescindir de la parte decimal e iterar sólo hasta el entero más cercano por defecto.
La mejora del algoritmo anterior sería la siguiente:
const elementos = 100;
const primos = [];
let iteraciones = 0;
for(let candidato = 2; candidato <= elementos; candidato++) {
let primo = true;
let maximoDivisor = Math.floor(Math.sqrt(candidato));
for(let divisor=2; divisor <= maximoDivisor; divisor++) {
iteraciones++;
if(candidato%divisor == 0) {
primo = !primo;
break;
}
}
if(primo) primos.push(candidato);
}
console.log(`iteraciones: ${iteraciones}`);
console.log(primos);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Hemos reducido la cantidad de iteraciones a 236 iteraciones!!! para obtener el mismo resultado. ¿Se podrá hacer aún más eficiente?.
Criba de Eratóstenes
En la Criba de Eratóstenes, se pide escribir todos los números naturales desde 2 hasta N, luego, comenzando por 2, se recorre toda la lista marcando (tachando) todos los múltiplos de 2. Luego se hace lo mismo con el valor siguiente de la lista que no haya sido tachado (por ejemplo 3), y así se va avanzando hasta que hayamos tachado todos los números compuestos que hay entre 2 y N. Al final, los números que no hayan sido tachados en nuestra criba, serán precisamente los números primos que buscamos.
El algoritmo sería algo como esto:
- Se crea una lista con todos los números de 2 a N.
- Se itera desde i=2 hasta i <= Math.floor(Math.sqrt(N)) (por lo que vimos anteriormente)
- Si i no ha sido tachado, se itera desde j=i hasta Math.floor(N/i) y se tacha cada múltiplo de i (i*j) en la lista.
- Cuando se termina la iteración del paso 2, los números primos serán aquellos que no han sido tachados en la lista.
Un ejemplo (tomado de Wikipedia):
Para implementar este algoritmo en Javascript, podemos hacer lo siguiente:
- Se crea una lista de elementos desde 2 hasta N:
const elementos = 100;
const criba = (new Array(elementos - 1)).fill(1);
En el código anterior, hemos creado un Array de 99 elementos (de 2 a N hay N - 1 elementos), y este Array lo hemos llenado con unos.
- Se itera desde i=2 hasta i<=Math.floor(Math.sqrt(N)):
const maxDivisor = Math.floor(Math.sqrt(elementos));
for(let i = 2; i <= maxDivisor; i++) { ... }
En el código anterior se calcula la raíz cuadrada de N y se crea un bucle for que va desde 2 hasta dicho valor.
- Si i no ha sido tachado, se itera desde j=i hasta Math.floor(N/i) y se tacha cada múltiplo de i (i*j) en la lista.
//dentro del bucle for
// i representa el número que estamos probando, su posición en la lista es: i - 2
// si criba[i - 2] vale 1 significa que no ha sido tachado
if(criba[i - 2]) {
//iteramos hasta Math.floor(elementos/i) ya que multiplicaremos i por j (múltiplos de i)
//entre i y N hay N/i múltiplos
for(let j = i; j <= Math.floor(elementos/i); j++){
criba[(i*j) - 2] = 0; // recordar que debemos restar 2 para indicar el índice correcto
}
}
En el código anterior, se tacha cada múltiplo del valor que se está iterando estableciendo su valor en la lista a cero.
- Cuando se termina la iteración del paso 2, los números primos serán aquellos que no han sido tachados en la lista.
const primos = [];
criba.forEach((primo, index) => {
if(primo) primos.push(index + 2);
});
console.log(primos);
En el código anterior se crea un Array llamado primos y se recorre la criba. Por cada elemento no tachado (cuyo valor es 1) se guarda en el Array de primos su posición sumada con 2 (index + 2), que será el valor del primo.
Una implementación de este algoritmo podría ser:
const elementos = 100;
const primos = [];
const criba = (new Array(elementos - 1)).fill(1);
let iteraciones = 0;
const maxDivisor = Math.floor(Math.sqrt(elementos));
for(let i = 2; i <= maxDivisor; i++) {
if(criba[i - 2]) {
for(let j = i; j <= Math.floor(elementos/i); j++){
criba[(i*j) - 2] = 0;
iteraciones++;
}
}
iteraciones++;
}
criba.forEach((element, index) => {
if(element) primos.push(index + 2);
});
console.log(`iteraciones: ${iteraciones}`);
console.log(primos);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Notemos que este algoritmo es aún más eficiente que los dos anteriores, ya que, quitando el hecho de que debemos crear la lista de números y luego recorrer la misma para sacar los primos, se logra el resultado en tan solo 113 iteraciones!!!.
Espero que esto deje clara las diferentes formas de lograr el objetivo, siendo la Criba de Eratóstenes una de las más eficientes.
Usando un generador (ES6)
Una posibilidad es utilizar un generador para simplemente iterar sobre el mismo y que en cada iteración se devuelva el siguiente número primo de la secuencia.
La idea es sencilla y no se necesita almacenar los valores primos, lo que se hace es tomar la idea planteada en la criba de Eratóstenes y crear una estructura iterable que implemente el método next()
, de tal forma que en cada llamada a dicho método se devuelva un valor primo y así podemos mostrar los primeros n
enteros primos.
Lo primero es tener una forma de iterar los números naturales, dado un valor inicial. Podemos escribir una función generadora que devuelva la secuencia de números naturales (desde un valor n) cada vez que se llame a la función next()
de la secuencia.
Por ejemplo:
// generador de números naturales
const naturales = function* (inicio) {
inicio = inicio < 1 ? (inicio === 0 ? 1 : -inicio) : inicio; // los naturales no son negativos
yield inicio;
yield* naturales(inicio + 1);
}
// creamos la secuencia que empiece en 1
const seq = naturales(1);
// mostramos los primeros 10 naturales:
for (let i = 0; i< 10; ++i) {
console.log(seq.next().value);
}
.as-console-wrapper {
min-height: 100%;
top: 0;
}
Ahora necesitamos crear una función generadora que tome cada valor de la secuencia de números naturales y dado un primo, me devuelva todos los valores que no sean múltiplos de dicho primo. Esto es una criba sobre una secuencia de valores.
Por ejemplo:
const criba = function* (seq, primo) {
for (let num of seq) {
if (num % primo !== 0) {
yield num;
}
}
}
Esta función recorre una secuencia de números y devuelve aquellos que no sean múltiplos de primo
.
Ahora que tenemos estas 2 funciones que devuelven una secuencia, podemos escribir otra función generadora que a partir de un valor inicial devuelva el siguiente valor primo. Esto lo logramos reescribiendo la secuencia de valores naturales por aquella que tenga los valores no múltiplos del primo anterior.
Por ejemplo:
const primos = function* (seq) {
let primo = seq.next().value;
yield primo;
seq = criba(seq, primo);
yield* primos(seq);
}
En esta función se recibe una secuencia que (idealmente) inicia en un valor primo (supongamos el 2). Luego, por cada valor de la misma, crea una nueva secuencia que contiene sólo los números que no son múltiplos del primo generado, y devuelve dicho valor en cada llamado a next()
.
Un ejemplo del código anterior funcionando para mostrar los primeros 10 primos sería:
const naturales = function* (inicio) {
inicio = inicio < 1 ? (inicio === 0 ? 1 : -inicio) : inicio; // los naturales no son negativos
yield inicio;
yield* naturales(inicio + 1);
}
const criba = function* (seq, primo) {
for (let num of seq) {
if (num % primo !== 0) {
yield num;
}
}
}
const primos = function* (seq) {
let primo = seq.next().value;
yield primo;
seq = criba(seq, primo);
yield* primos(seq);
}
const p = primos(naturales(2));
// mostrar los primeros 10 valores primos
for(let i = 0; i < 10; ++i) {
console.log(p.next().value);
}
.as-console-wrapper {
min-height: 100%;
top: 0;
}
Si bien este algoritmo tal vez no sea tan eficiente como los presentados con anterioridad, es otra forma de obtener valores primos usando generadores de Javascript para obtener una secuencia que siempre devolverá un valor primo cada vez que se llame al método next()
.