0

Мне попалась задача, суть такова: сложить делители числа 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

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

3
  • Я поправил метки. Поищите на этом сайте "факторизацию". Их очень много. Число ваше совсем не большое. 8 мар в 20:23
  • И ещё: сумма делителей отыскивается без поиска самих делителей: функция делителей. 8 мар в 20:24
  • 1
    Вообще-то совершенных чисел так мало, что проверять смысла нет. Проще сделать табличку :) Даже на oeis их всего десяток привели...
    – Harry
    8 мар в 20:28

1 ответ 1

0

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.