Как оптимизировать алгоритм для нахождения числа с 500 делителями?

Question

[Umid]

Есть последовательность треугольных чисел.
Нади найти такое треугольное число, у которого более 500 делителей.
Есть алгоритм:

var result = 0;
var resultArray = []; // Массив треугольных чисел
var measureList = []; // Массив делителей

for (let i = 1; i <= 1000; i++) {
	result =  i + result;
	resultArray.push(result);

	function getMeasure(result) {
		console.log(result); //Выводим наибольшее треугольное число которое получилось.
		for (let k = 1; k <= result; k++) {
			let measure = result / k;
			if(measure % 1) {

			} else {
				measureList.push(measure);
			}
		}
	}

	if(i == 1000) {
		getMeasure(result);
	}
}

console.log(measureList);

Данный код срабатывает моментально.

Но чтобы найти число с 500 делителями , придётся очень долго ждать (Даже очень долго).

Для этого необходимо в начале цикла for: i <= 1000 заменить на i <= 1000000(Взял значение на глаз).

Никак не могу додуматься до оптимального алгоритма.
Может что почитать?

Answer 1

[Rsa97]

Для разложения числа на множители проверяют не все варианты подряд, а только простые числа. Таблицу можно подготовить заранее или генерировать в программе. Для разложения числа N₀ надо проверять простые числа до N₀^1/2 включительно. После каждого найденного множителя текущее значение N_i делится на него и перебор простых чисел начинается сначала.
Получается разложение вида
N₀ = p₁^n₁·p₂^n₂·...·p_k^n_k, где p_i - все простые числа от 2 до N₀^1/2.
Количество различных делителей K получается как количество комбинаций степеней
K = (n₁+1)·(n₂+1)·...·(n_k+1)
На примере:
N₀ = 72
Простые числа до 72^1/2: p_i = [2, 3, 5, 7]
Инициализируем счётчики степеней: n_i = [0, 0, 0, 0]
72 на 2 делится, n₁ = 1, проверяем 72/2 = 36
36 на 2 делится, n₁ = 2, проверяем 36/2 = 18
18 на 2 делится, n₁ = 3, проверяем 18/2 = 9
9 на 2 не делится
9 на 3 делится, n₂ = 1, проверяем 9/3 = 3
3 на 2 не делится
3 на 3 делится, n₂ = 2, 2/3 = 1, закончили поиск.
Получили массив степеней: n_i = [3, 2, 0, 0]
Количество делителей: K = (3+1)·(2+1)·(0+1)·(0+1) = 12

Comments

[Umid]

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

[Rsa97]

Umid: Тогда вам лучше начать со школьного курса математики за 6 класс.

[Umid]

Всё, догнал. Спасибо большое.

[mentosdOpe]

Rsa97, "Тогда вам лучше начать со школьного курса математики за 6 класс."

Чел, ты с таким апломбом лучше бы посмотрел на строчку, где после делимости на 3 ты проверяешь делимость на 2 аааааааааа. Вот это реально материал за 6 класс. Можно ли нечётное число, разделив на 3, сделать чётным.