I am trying to find friendly numbers among the first 10000 numbers.
Friendly numbers means that the divisors of a number added are equal to the other and then they are friends.
In this code, equal numbers are not taken into account.
I have managed to find them and make a functional code but when I run it it takes 13min to find the 10000 numbers.
var num1;
var num2;
function divisor (x){
var suma = 0;
for(var k=1;k<= Math.floor(x/2) + 1; k++){
if(x%k ==0){
suma = suma + k;
}
}
return suma;
}
for(var a = 2; a<10000; a++ ){
num1 = divisor(a);
for(var b= a; b<10000; b++){
num2 = divisor(b);
if(num1 == b && num2 == a && a<b){
console.log(a + ' y ' + b + ' son amigos' + '\n');
}
}
}
You are doing the calculation multiple times
divisor
that it is a quite heavy function.In my solution I first create a
Objeto
with the calculation of all divisors. Then with the calculations done I proceed to look for friends.I can think of two ways to streamline the algorithm.
We can go through the numbers of
1
aMath.sqrt(x)
, beingx
the number of which we want the sum of the divisors. We know that the largestdivisor of will be , if it is even. So we don't need to iterate through the numbers in a .
x
x / 2
x
x / 2
x
On the other hand, since in the algorithm we have two loops , it means that we are doing calculations of duplicate divisors.
Therefore, we can store the calculations already made to reuse them the next time they are needed. So the sum of divisors of each number is only calculated once.
This is how the entire script would look.
The result is a bit immediate.
In 200ms , approximately.
I hope it works.