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

Question

Прохожу курс по JS и попал на задачу:

Сделайте функцию getFreindly, которая будет находить пары дружественных чисел в промежутке (1, 3000) и возвращать их в виде двухмерного массива.

Вроде бы решил данную задачу так:

function getOwnDivisors(num) {
    let arr = [];

    for (let i = 1; i < num; i++) {
        if (num % i === 0) {
            arr.push(i);
        }
    }

    return arr;
};

console.log(getOwnDivisors(220));

function getSum(num) {
    let sum = 0;

    for (let item of num) {
        sum += item;
    }

    return sum;
};

console.log(getSum(getOwnDivisors(220)));


function isFriendly(num1, num2) {
    let sum1 = getSum(getOwnDivisors(num1));
    let sum2 = getSum(getOwnDivisors(num2));

    if (sum1 == num2 && sum2 == num1) {
        return true;
    }
    return false;
};

console.log(isFriendly(220, 284));

function getFriendly(start, end) {
    let arr = [];

    for (let i = start; i < end; i++) {
        for (let j = i + 1; j < end; j++) {
            if (isFriendly(i, j)) {
                arr.push([i, j]);
            }
        }
    }
    return arr;
};

console.log(getFriendly(1, 3000));

Но, данное решение прям очень нагружает пк, и выводит результат слишком долго, хотел узнать способ решение данной задачи, что бы код обрабатывался как можно быстрее.Либо посоветуйте куда обратить внимание.

Как понял я, все из-за getFriendly() в большом дипазоне, слишком много нужно перебирать цикл в цикле.

Больше всего интересует как изменить именно функцию getFriendly(), не трогая остальной код.

Спасибо)

Answer 1

Я не настоящий js сварщик, но чуточку могу. Посмотрим в код - видим один паттерн - конструкцию getSum(getOwnDivisors(num)). явно нужно заменить на одну функцию

function getAll(num) {
  return getSum(getOwnDivisors(num));
}

и исправляем рядом функцию isFriendly

function isFriendly(num1, num2) {
    let sum1 = getAll(num1);
    let sum2 = getAll(num2);

    return (sum1 == num2 && sum2 == num1);
};

Запускаем и проверяем, что работает также медленно (у меня от 1 до 1000 было порядка 3 секунд)

теперь переписываем функцию getAll

var mm = new Map();
function getAll(num) {
  var v = mm.get(num);
  if (v !== undefined) {
    return v;
  }
  v = getSum(getOwnDivisors(num));
  mm.set(num, v);
  return v;
}

(да, я знаю, я сделал глобальную мапу, но я по другому не умею в js). Теперь снова запускаем и получаем что то в районе 0.1 секунды. Уже лучше. Запускаем до 10000 - полторы секунды. лучше. Но хочется ещё лучше. Я буквально чуточку выжал, делая цикл до num/2.

Но хочется ведь быстрее и попроще. Переписал функцию немного через массив (не верил, что так работает)

var mm = [];
function getAll(num) {
  var v = mm[num];
  if (v !== undefined) {
    return v;
  }
  v = getSum(getOwnDivisors(num));
  mm[num] = v;
  return v;
}

и скорость стала просто чудесной - 0.4 секунды для диапазона до 10000. Думаю, это нормально.

БЛОГ НА HUSL

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

Ответы (1 шт):