Где ошибка и где можно рациональнее написать код, чтобы сократить время обработки?

Question

[Олег]

Всем привет, при решении задачи столкнулся с проблемой, сначала код вообще не работал, через какое-то время срабатывает периодически. Это с заданием сделать функцию getFrendly(), которая будет находить дружественные числа в промежутке от 1 до 3000 и выводить в двухмерный массив.
Вот мой код:

/* Если у нас есть два числа и сумма одного
 числа равна делителям другого и наоборот, 
 то такая пара чисел называется дружественными. */

/* Решим задачу на определение дружественных чисел.
Числа являются дружественными, если сумма собственных 
делителей (с числом 1, но без самого числа) первого числа 
равна второму числу и, наоборот, сумма делителей второго 
числа равна первому. */


function isFrendly (num1, num2){
  return getSumDivisors(num1) === num2 && getSumDivisors(num2) === num1;
}

//Функция на поиск делителей числа, без самого числа
function getDivisors(num){
  let divisorsNum = [];
  for (i = 1; i < num; i++ ){
    if (num % i === 0){
      divisorsNum.push(i);
    }
  }
  return divisorsNum;
}
//Нахождение суммы
function getSum(arr){
  let sum = 0;
  for (i = 0; i < arr.length; i ++){
    sum += arr[i];
  }
  return sum;
}

//Нахождение суммы делителей
function getSumDivisors (num) {
  return getSum(getDivisors(num));
}

/* Сделайте функцию getFrendly, которая будет находить
пары дружественных чисел в заданном промежутке и 
возвращать их в виде двухмерного массива */

function getFrendly() {
  let arrFriendly = [];
  for (j = 1; j <= 3000; j++){
    for (k = j + 1; k <= 3000; k++){
      if (isFrendly(j, k) == true && j !== k ){
       arrFriendly.push([j, k]);
      }
    }
  }
  return arrFriendly;
}

console.log(getFrendly());

Comments

[Олег]

Я наверное не совсем верно поставил вопрос, по сути код работает, но тут 100% не рационально он написан, особенно в функции getFrendly() и там есть ошибка, хочу чтобы кто-то более знающий дал оценку и подсказал, как оптимизировать.

И подскажите не могу понять, почему в функции getFrendly(), если в цикле я буду использовать i, а не k и j, функция не работает, но когда не использую i, то все работает, это из-за того, что у меня во вспомогательных функциях уже используется переменная i ???

Answer 1

[Сергей Соколов]

тут долгая и «дорогая» задача — нахождение суммы делителей числа. У вас в решении для одного (любого) числа она вычисляется по многу раз. Этого нужно избежать.

Составьте словарь: объект или Map, где ключ – сумма делителей. А значение – массив чисел, у которых оказалась такая сумма делителей.

Один раз пройдитесь по диапазону 1 ... 3000 и заполните словарь, посчитав сумму делителей для каждого по одному разу.

Затем остаётся пройти по словарю и набрать из каждого из массивов значений, пары. Например, все простые числа свалятся в массив под ключом 1 (все делятся только на 1 и на себя). {1: [1, 2, 3, 5, 7, 11, 13, ... ], ... } Из этого массива нужно все возможные пары повытаскивать: [1, 2], [1, 3], [1, 5], ..., [2, 3], [2, 5], ...

Ещё оптимизация: при поиске делителей числа есть смысл проверять не до самого числа, а только до его половины. Например, 21: проверить, делится, ли на 2, 3, 4, ... 10 <= (21 / 2 = 10.5) и дальше проверять не нужно.

Comments

[Олег]

Спасибо!

Answer 2

[black1277]

Зачем внутри getDivisors создавать массив, а потом писать отдельную ф-ю для складывания массива? Можно было сразу складывать в результат и возвращать сумму.
По поводу использования i - вы не объявляли её внутри for, поэтому в нестрогом режиме она стала глобальной. Если объявлять внутри
for (let i = 0; i < arr.length; i ++)
то она будет локализована внутри цикла и проблем в других местах не будет.
Для продвинутой работы с массивами, рекомендую ознакомиться с функциями reduce и map

Comments

[Олег]

Спасибо, ошибку понял)