Как ускорить функцию подсчёта суммы от 0 до заданного числа js?

Question

[Zold09]

Как ускорить функцию подсчёта суммы от 0 до заданного числа js?

приветствую, я ещё только учусь js. Решил задачку, но возник вопрос. При вводимых числах до 1 000 000, принципе функция быстро выполняется, а вот ближе к 1 000 000 и выше, долго, Как можно модифицировать этот код, чтоб с большими значениями тоже быстро работало?

по заданию - написать функцию которая принимает число введённое пользователем в поле ввода и суммирует числа от 0 до введённого числа которые делятся на 3 или на 5. Результат вывести на страничке , вместо поля ввода.

Вот я состряпал такое месиво:

let input = document.querySelector('#input');
let btn = document.querySelector('.button');
let section = document.querySelector('.num');
let form = document.querySelector('form');
let arrNum = [];

let arr = (input) => {
    btn.addEventListener('click', (e) => {
        if (e.target) {
            let count = 0;
            let numValue = Number(input.value);

            //собираю массив:arrNum из заданного числа numValue
            while (count < numValue) {
                (count % 3 === 0 || count % 5 === 0)
                    ? arrNum.push(count)
                    : section.innerHTML = `Чёт ничё не делится, ни на 3, ни на 5`;
                count++;
            };

            //
            (arrNum.length > 0)
                ? section.innerHTML = `${arrNum.reduceRight((sum, current) => sum + current)}`
                : (arrNum.length === 0)
                    ? section.innerHTML = `А суммировать то нечего ${arrNum}`
                    : section.innerHTML = `Массив arrNum - пустой или там только 1 знаечние.`
        }
    })

}
arr(input);

<main class="main container">
     <section class="num">
         <form action="#" class="form">
            <lebal class="lebal" from="input"></lebal>
            <input type="text" name="input" id="input">
            <button class="button">посчитать</button>
         </form>
     </section>
    </main>

Comments

[Alexandroppolus]

сегодня "день тройки и пятерки", что ли? ))
https://qna.habr.com/q/1149280

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

// вместо
(arrNum.length > 0)
  ? section.innerHTML = `${arrNum.reduceRight((sum, current) => sum + current)}`
  : (arrNum.length === 0)
    ? section.innerHTML = `А суммировать то нечего ${arrNum}`
    : section.innerHTML = `Массив arrNum - пустой или там только 1 знаечние.`

// лучше
section.innerHTML =
  arrNum.length > 0
    ? `${arrNum.reduceRight((sum, current) => sum + current)}`
    : arrNum.length === 0
    ? `А суммировать то нечего ${arrNum}`
    : `Массив arrNum - пустой или там только 1 знаечние.`;

Answer 1

[Rsa97]

const n3 = Math.floor(n / 3);
const n5 = Math.floor(n / 5);
const n15 = Math.floor(n / 15)
const sum = (n3 * 3 * (n3 + 1)  + n5 * 5 * (n5 + 1) - n15 * 15 * (n15 + 1)) / 2;

Answer 2

[Михаил]

А зачем тут массив? Сразу в цикле складывайте в аккумулятор.
Уберите из цикла обращение к innerHTML - это очень медленно.

Мало того, есть формулы суммы арифметической прогрессии. Чтобы найти сумму чисел, которые делятся на 3 или на 5 нужно:

Сумма чисел, которые делятся на 3 + сумма чисел, которые делятся на 5 - сумма чисел, которые делятся на 15.

Таким образом, подсчет данных сумм выполняется даже без циклов, по математическим формулам.

Answer 3

[Антон Антон]

Воспользоваться мозгом и посчитать, сколько чисел делится на 3 нацело (n3), на 5 нацело (n5), на 15 нацело (n15) в диапазоне.
Затем по формуле суммы n первых чисел арифметической прогрессии посчитать сумму n3 последовательности с шагом 3 + сумму n5 членов последоват1льности с шагом 5 - сумма n15 членов последовательности с шагом 15 и получить сложность вычисления O(1) вместо O(n)
Да и в имеющемся коде зачем-то создается и расширяется массив (много-много раз происходит выделение памяти), затем выполняется его обход. тупо избавившись от него и считая сразу в один цикл получится в несколько раз ускорение.

Comments

[Юрий Иванов]

Очень грубо, минус за коммуникацию

Answer 4

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

const sum = number => {
  if (number < 0) return 0;

  // вспомогательная функция считает сумму ряда с шагом step
  const sequenceSum = step => {
    const q = Math.floor(number / step);
    return q * (q + 1) * step / 2;
  }

  return sequenceSum(3) + sequenceSum(5) - sequenceSum(3 * 5);
}

// использование
sum(999999) // мгновенно: 233333166668

via