Se me ocurren dos formas de agilizar el algoritmo.
- Cálculo de la suma de divisores
Podemos recorrer los números de 1
a Math.sqrt(x)
, siendo x
el número del cual queremos la suma de los divisores.
Sabemos que el divisor más grande de x
será x / 2
, si x
es par. De modo que no nos hace falta recorrer los números de x / 2
a x
.
const calcSumOfDiv = x => {
// La suma empieza en 1, porque siempre será un divisor.
let sum = 1;
// El loop empezará en 2 (para no repetir el 1)
// Y llegará hasta Math.sqrt(x). Haciendo el cuadrado de i, es lo mismo.
for (let i = 2; i * i < x; ++i) {
if (x % i === 0) {
sum += i;
// Debemos también contemplar el caso de los mayores
// por la propiedad conmutativa.
// Siendo x par, si i = 2, i es divisor y también x / 2.
// Así que sumamos ambos.
// Excepto el caso de cuadrados perfectos
if (x / i !== i) {
sum += x / i;
}
}
}
return sum;
}
- Almacenamiento de cálculos
Por otra parte, como en el algoritmo tenemos dos loops, significa que estamos haciendo cálculos de divisores duplicados.
for(let a = 2; a < LENGTH; a++) {
for(let b = a; b < LENGTH; b++) {
// En la primera iteración del loop interno,
// La suma de divisores de a ya se ha calculado, pero b = a y se vuelve a calcular para a
}
// En la siguiente vuelta, a será a + 1, pero la suma de divisores de a + 1
// ya la tenemos calculada cuando recorrimos el loop en b.
}
Por ello, podemos almacenar los cálculos ya hechos para reaprovecharlos la siguiente vez que vayan a necesitarse. De modo que sólo se calcula la suma de divisores de cada número una única vez.
// Aquí guardamos los cálculos. La clave es el número y el valor su suma de divisores
const map = {
1: 1
};
// Cuando querramos sacar el cálculo, primero vemos si lo tenemos ya.
// Si NO es el caso, lo calculamos y lo guardamos.
const sumOfDiv = x => {
if (!map[x]) map[x] = calcSumOfDiv(x);
return map[x];
}
Así quedaría el script entero.
const LENGTH = 10000;
const map = {
1: 1
};
const calcSumOfDiv = x => {
let sum = 1;
for (let i = 2; i * i < x; ++i) {
if (x % i === 0) {
sum += i;
if (x / i !== i) {
sum += x / i;
}
}
}
return sum;
}
const sumOfDiv = x => {
if (!map[x]) map[x] = calcSumOfDiv(x);
return map[x];
}
const areAmicable = (x, y) =>
x !== y &&
sumOfDiv(x) === y &&
sumOfDiv(y) === x;
for(let a = 2; a < LENGTH; a++) {
for(let b = a; b < LENGTH; b++) {
if (areAmicable(a, b)) {
console.log(`${a} and ${b} are amicables.`);
}
}
}
El resultado es un poco inmediato.
220 and 284 are amicables.
1184 and 1210 are amicables.
2620 and 2924 are amicables.
5020 and 5564 are amicables.
6232 and 6368 are amicables.
algorithm: 203.038ms
En 200ms, aproximadamente.
Espero que sirva.
a
, encontramos ab
,c
, etc. ¿no sería lógico que al buscar los amigos ded
, los números anteriormente obtenidos (eg: a, b, c
) no sean considerados? – Marcos el 21 may. 20 a las 17:27