Алгоритм нахождения всех делителей большого числа

Question

Мне попалась задача, суть такова: сложить делители числа n и сравнить сумму с самим n. Но вопрос не про это - вопрос в том, чтобы найти эти делители для огромных чисел, например, для 23_459_879_034.

function isPerfect(n) {
    let divisors = 0;
    let divisorsSum = 0;

    while (divisors <= n / 2) {
        if (n % divisors === 0) {
            divisorsSum += divisors;
        }

        divisors++;
    }

    return divisorsSum === n;
}

console.log(isPerfect(23459879034));
// true

Данный код выполняется очень медленно. Какой алгоритм можно применить, чтобы найти все делители?

Answer 1

Вообще-то совершенных чисел так мало, что проверять смысла нет. Проще сделать табличку :) Даже на oeis их всего десяток привели...

Но если ну очень хочется посчитать, я бы начинал с того, что делил на 2, пока делится, считая, сколько раз это удается (пусть k). Потом к тому что осталось, прибавлял бы 1 и опять смотрел — степень ли это двойки? И только если да, причем на одну большая, чем k, вот тогда и только тогда я бы стал выяснять, а не простое ли число 2^k+1-1.

Потому что все известные ныне совершенные числа имеют вид 2^k-1(2^k-1), при этом (2^k-1) — должно быть простое число.

А что до поиска всех делителей, то, как вам уже советовали, посмотрите это.

Answer 2

меньший из двух делителей всегда будет меньше корня из исходного числа -> перебирать числа до корня, если делится на исходное, то больший делитель находить делением на текущее перебираемое

БЛОГ НА HUSL

Алгоритм нахождения всех делителей большого числа

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