Propongo el siguiente algoritmo, si bien se basa en la idea de @the-breaker, la diferencia es que en este no se calcula el factorial usando la multiplicación de todos los números desde 1 hasta N, sino que lo calcula multiplicando los factores primos hallados, ya que me parece que es la aproximación más adecuada al problema planteado.
La idea planteada es que se pueden descomponer los elementos que comprenden un factorial en sus factores primos:
7! = 2 * 3 * 4 * 5 * 6 * 7
7! = 2 * 3 * (2 * 2) * 5 * (2 * 3) * 7
7! = 2^4 * 3^2 * 5 * 7
Luego se calcula el factorial multiplicando estos factores primos (elevados cada uno a su respectivo exponente).
Usando la premisa divide y vencerás, vamos a dividir el problema en tareas pequeñas y puntuales necesarias para obtener la solución. Por lo tanto estas serán las funcionalidades específicas:
- Función que indique si un número es primo o no.
- Función que descomponga un número compuesto en factores primos.
- Método para agrupar factores comunes con su exponente.
- Cálculo del factorial usando los factores primos.
Con estas 4 funcionalidades podemos armar un algoritmo eficiente. Tal vez exista una manera aún más eficiente de hacer el trabajo, pero esta es la que se me ocurrió a mi.
Función para determinar si un número es primo.
Esta es una función de esas que siempre debemos tener guardada como herramienta básica, existen algunos algoritmos que buscan optimizar esta función, pero eso ya está fuera del alcance del objetivo básico que nos planteamos aquí.
const isPrime = (x) => {
const CRIBA = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
if( x < 2) {
return false;
} else if(CRIBA.indexOf(x) > -1) {
return true;
} else if(CRIBA.some((primo) => { return (x % primo === 0) })) {
return false;
} else {
if(x <= CRIBA[CRIBA.length - 1] * 2) {
return true;
} else {
let test = true;
for(let i = CRIBA[CRIBA.length - 1] + 1; i <= Math.floor(x/2); i++) {
if(x % i === 0) {
test = false;
break;
}
}
return test;
}
}
}
console.log(`7 es primo: ${isPrime(7)}`);
console.log(`11 es primo: ${isPrime(11)}`);
console.log(`6 es primo: ${isPrime(6)}`);
console.log(`37 es primo: ${isPrime(37)}`);
Esta función usa una lista con números primos conocidos. Muchos algoritmos se basan en lista de números primos ya calculados para intentar obtener valores de primos más altos con una eficiencia superior a la iteración desde 2 hasta N/2. En este caso he usado una criba con 10 números primos, pero se puede ajustar a gusto.
¿Porqué hasta la mitad del número? La respuesta es simple: nos ahorramos algunas iteraciones, ya que un número compuesto no puede tener un factor primo mayor a la mitad de su valor.
¿Porqué un valor menor que el doble del mayor primo de la lista es un número primo? Muy sencillo, si P es el mayor primo de la lista y N es menor o igual que 2P, entonces esto indica que la validación N % p === 0 dio falso para todos los p de la lista, y como hemos dicho que un número compuesto no puede tener un factor primo que sea mayor a la mitad de su valor, entonces debe ser primo.
Solamente se itera cuando un valor dado es mayor que 2P, además se itera desde P+1 hasta N/2.
Descomposición en factores primos
Teniendo una forma de determinar si un número es primo o no, podemos ahora descomponer en factores primos. El siguiente algoritmo toma un valor N y prueba si el mismo es primo o no. Si lo es, devuelve una lista con N como elemento único. Si N es compuesto, realiza una división de N por cada primo posible entre 2 y N/2. Por cada división exacta que se logre, se agrega el primo a la lista y se divide N por el primo, y se realiza una nueva división. La iteración de cada división se detiene cuando la división es inexacta y se pasa a verificar el siguiente primo de la lista. El valor de N se va actualizando en cada paso hasta obtener todos los primos.
const isPrime = (x) => {
const CRIBA = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
if( x < 2) {
return false;
} else if(CRIBA.indexOf(x) > -1) {
return true;
} else if(CRIBA.some((primo) => { return (x % primo === 0) })) {
return false;
} else {
if(x <= CRIBA[CRIBA.length - 1] * 2) {
return true;
} else {
let test = true;
for(let i = CRIBA[CRIBA.length - 1] + 1; i <= Math.floor(x/2); i++) {
if(x % i === 0) {
test = false;
break;
}
}
return test;
}
}
}
const primeFactors = (x) => {
if(isPrime(x)) return [x];
let p = [];
let value = x;
for(let i = 2; i <= Math.floor(x/2); i++) {
if(isPrime(i)) {
while(value % i === 0) {
value = value / i;
p.push(i);
}
}
}
return p;
}
console.log(primeFactors(6).join(' - '));
console.log(primeFactors(12).join(' - '));
console.log(primeFactors(17).join(' - '));
console.log(primeFactors(256).join(' - '));
Agrupar factores comunes
Usaremos el método reduce(); para contar los factores primos y agruparlos en un array de objetos. Cada objeto tendrá la forma {<clave>: <valor>, ... }, donde la <clave> será el factor primo y el <valor> será el exponente (cantidad de veces que aparece).
const groupFactors = (factors) => {
return factors.reduce((all, f) => {
if(f in all) {
all[f]++;
} else {
all[f] = 1;
}
return all;
}, {});
}
console.log(groupFactors([2,2,2,3,3,5]));
Calcular Factorial usando los factores primos
Ahora simplemente debemos calcular el factorial usando los factores primos hallados, para ello recorreremos el objeto creado con los factores agrupados y realizaremos las operaciones matemáticas correspondientes.
const groupFactors = (factors) => {
return factors.reduce((all, f) => {
if(f in all) {
all[f]++;
} else {
all[f] = 1;
}
return all;
}, {});
}
const obj = groupFactors([2,2,2,3,5]); // esto es 5!
let factors = [];
let factorial = [];
Object.keys(obj).forEach((k) => {
factors.push(`${k}${obj[k] > 1 ? `^${obj[k]}`: ''}`);
factorial.push(k ** obj[k]);
});
console.log(`El factorial de 5 es ${factorial.reduce((acc,curr) => acc * curr)}`);
console.log(`La descomposición en factores primos de 5! es:`);
console.log(`${factors.join(' * ')}`);
Ensamblando todo
El paso final es escribir una función que realice toda la tarea en un solo llamado, todas nuestras funciones deben estar diponibles para realizar esta tarea, por lo tanto el código podría verse así:
const isPrime = (x) => {
const CRIBA = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
if( x < 2) {
return false;
} else if(CRIBA.indexOf(x) > -1) {
return true;
} else if(CRIBA.some((primo) => { return (x % primo === 0) })) {
return false;
} else {
if(x <= CRIBA[CRIBA.length - 1] * 2) {
return true;
} else {
let test = true;
for(let i = CRIBA[CRIBA.length - 1] + 1; i <= Math.floor(x/2); i++) {
if(x % i === 0) {
test = false;
break;
}
}
return test;
}
}
}
const primeFactors = (x) => {
if(isPrime(x)) return [x];
let p = [];
let value = x;
for(let i = 2; i <= Math.floor(x/2); i++) {
if(isPrime(i)) {
while(value % i === 0) {
value = value / i;
p.push(i);
}
}
}
return p;
}
const groupFactors = (factors) => {
return factors.reduce((all, f) => {
if(f in all) {
all[f]++;
} else {
all[f] = 1;
}
return all;
}, {});
}
const factorialPrimeFactors = (x) => {
// casos no válidos
if(x < 1) {
console.log(`El factorial de ${x} no está definido`);
return;
}
if(x == 1) {
console.log(`El factorial de ${x} es ${x}.`);
return;
}
let primos = [];
for(let i = 2; i <= x; i++) {
primos.push(... primeFactors(i));
}
const obj = groupFactors(primos);
let factors = [];
let factorial = [];
Object.keys(obj).forEach((k) => {
factors.push(`${k}${obj[k] > 1 ? `^${obj[k]}`: ''}`);
factorial.push(k ** obj[k]);
});
console.log(`El factorial de ${x} es ${factorial.reduce((acc,curr) => acc * curr)}`);
console.log(`La descomposición en factores primos de ${x}! es:`);
console.log(`${factors.join(' * ')}`);
}
factorialPrimeFactors(17);
factorialPrimeFactors(120);
factorialPrimeFactors(25);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Espero que esto te de otra visión del problema y una solución alternativa al cálculo de un número factorial.
EDICIÓN
Gracias al comentario de @abulafia sobre optimización, edito la función que determina si un número es primo.
La idea planteada por @abulafia es simple:
Ningún número compuesto puede tener un factor primo mayor que su raíz cuadrada si ya hemos comprobado que hasta su raíz cuadrada no lo tiene. Por lo tanto si hasta llegar a la raíz cuadrada de un número, no hemos hallado ningún factor que lo divida, el número es primo.
Esto reduce significativamente las iteraciones que se realizan para determinar si un número es primo o no.
Usando la Criba de Eratóstenes, (la cual aplico de una forma trucada en mi algoritmo), e iterando hasta N/2 como sugerí en mi implementación tenemos por ejemplo, que si deseamos verificar si 103 es un número primo, entonces:
- Calculamos la mitad de 103 (al no ser exacto se toma sólo la parte entera del resultado), lo cual nos da la proximación de 51.
- Iteramos desde 2 hasta 51.
- En 50 iteraciones descubrimos que 103 es primo.
Usando la optimización comentada por @abulafia, ahora vamos a iterar solamente hasta la raíz cuadrada de 103, que nuevamente aproximaremos por defecto. El resultado real es 10,148891565, pero usaremos 10. Así las iteraciones son mucho menos para descubrir que 103 es primo:
- Calculamos la raíz de 103 y la aproximamos por defecto.
- Iteramos desde 2 hasta 10.
- En 9 iteraciones descubrimos que 103 es primo.
Nos hemos ahorrado 41 iteraciones. Es mucho más óptimo. El código de la función quedaría como el siguiente:
const isPrime = (x) => {
const CRIBA = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
if( x < 2) {
return false;
} else if(CRIBA.indexOf(x) > -1) {
return true;
} else if(CRIBA.some((primo) => { return (x % primo === 0) })) {
return false;
} else {
if(x <= CRIBA[CRIBA.length - 1] ** 2) {
return true;
} else {
// itero solo para números mayores que P^2, siendo P el mayor primo de mi lista
let test = true;
let count = 0;
for(let i = CRIBA[CRIBA.length - 1] + 1; i <= Math.floor(Math.sqrt(x)); i++) {
count++;
if(x % i === 0) {
test = false;
break;
}
}
console.log(`Iteraciones realizadas: ${count}`);
return test;
}
}
}
console.log('Comprobaremos si 1741 es un número primo (lo es)');
console.log('La aproximación de su raíz es 41');
console.log('Debemos realizar 40 iteraciones usando la Criba de Eratóstenes');
console.log('Sin embargo, dado que uso una versión trucada del mismo:');
console.log(`¿1741 es primo? ${isPrime(1741)}`);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Con esto tenemos un algoritmo más eficiente para determinar si un número es primo o no.
