Perfect Number

Q: Какова временная сложность проверки того, является ли число совершенным?

Сбор пар делителей до √n занимает время O(√n) и пространство O(1) . Для n = 10^8 это около 10^4 шагов. Проверка каждого кандидата до n / 2 имеет сложность O(n) — около 5 × 10^7 шагов для того же входного значения.

Q: Сколько совершенных чисел меньше 10^8?

Пять: 6 , 28 , 496 , 8128 и 33550336 . Они быстро становятся всё реже. Следующее число, 8589869056 , даже не помещается в 32-битное целое число.

Q: Существуют ли нечётные совершенные числа?

Никто не знает. Все найденные на данный момент совершенные числа чётные. В ходе поисков были исключены нечётные совершенные числа меньше 10^1500 , но нет доказательства, что их не может существовать. Ваша функция должна работать исходя из определения, а не из предположения, что входное значение чётное.

Q: В чём разница между совершенными, избыточными и недостаточными числами?

Сравни сумму собственных делителей с числом. Если они равны, число совершенное, например 28 . Если сумма больше, число избыточное, например 12 , сумма делителей которого равна 16 . Если сумма меньше, число недостаточное, как любое простое число, единственный собственный делитель которого — 1 .

НовичокМатематика и моделирование

+10

Собственный делитель n — это положительный делитель, меньший самого числа n. Совершенное число равно сумме своих собственных делителей: 6 = 1 + 2 + 3. Дан положительный целочисленный n. Верните true, если n — совершенное число, и false в противном случае.

Функция

isPerfect(n: integer) → boolean

ninteger: положительное целое число для проверки
Возвращаетboolean: true, если n равно сумме своих собственных делителей, иначе false

Ограничения

1 ≤ n ≤ 10⁸

Примеры

Ввод: n = 28
Вывод: true
Пояснение: Собственные делители числа 28 — это 1, 2, 4, 7 и 14. В сумме они дают 28, поэтому 28 — совершенное число.

Ввод: n = 12
Вывод: false
Пояснение: Собственные делители числа 12 — это 1, 2, 3, 4 и 6. В сумме они дают 16, что больше 12.

Ввод: n = 1
Вывод: false
Пояснение: У 1 вообще нет собственных делителей, поэтому сумма равна 0, а не 1.

+16 скрытых тестов при отправке

Дополнительный вопрос

Каждое чётное совершенное число имеет вид 2^(p-1) × (2^p-1), где 2^p-1 — простое число. Можешь перечислить все совершенные числа меньше 10^8 по этой формуле, не проверяя каждое число?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

В определении требуется сумма делителей, и очевидный цикл проверяет каждого кандидата вплоть до n / 2. Для n = 10^8 это 5 × 10^7 делений. Делители образуют пары, произведение которых равно n, поэтому можно собирать оба элемента каждой пары, проверяя кандидатов только до √n, то есть примерно 10^4 шагов.

Сложить все собственные делители

Верно, но не успевает на самых больших тестах

Идея

Следуй определению. Перебирай все значения d, начиная с 1, и, когда n % d == 0, добавляй d к текущей сумме. В конце сравни сумму с n. Для 28 цикл выбирает 1, 2, 4, 7 и 14, а 1 + 2 + 4 + 7 + 14 = 28.

Можно остановиться на n / 2. Делитель, отличный от n, оставляет частное не меньше 2, поэтому он никогда не превышает половину n. Это ограничение также подходит для n = 1: цикл выполняется ноль раз, сумма остается равной 0, а ответ — false.

Уменьшение диапазона вдвое не меняет темп роста. Для n = 10^8 цикл по-прежнему выполняется 5 × 10^7 раз, и так происходит для каждого входного значения такого размера, является ли оно делителем или нет.

Алгоритм

Присвойте total значение 0.
Переберите d от 1 до n / 2.
Если n % d == 0, добавьте d к total.
Верните результат проверки total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Соберите пары делителей до квадратного корня

Идея

Если d делит n, то и n / d делит его. Для 28 пары такие: 1 × 28, 2 × 14 и 4 × 7. В каждой паре один из множителей не больше √n, потому что произведение двух чисел, превышающих √n, больше n. Поэтому перебор до √n находит каждую пару ровно один раз, и по мере перебора ты складываешь оба множителя.

С двумя множителями нужно быть осторожнее. Пара 1 × n включает само число n, которое не является собственным делителем: начни с суммы 1 и перебор с 2. Для n = 1 такое начало неверно: его единственный делитель — оно само, поэтому сначала верни false. А когда n — квадрат, корень образует пару с самим собой: для 36 нужно прибавить 6 один раз, а не дважды.

Запиши условие границы как d * d ≤ n, чтобы обойтись целыми числами. При n = 10^8 цикл остановится на d = 10^4, поэтому он выполнится примерно 10^4 раз вместо 5 × 10^7.

Алгоритм

Если n == 1, вернуть false.
Установить total в 1, а d — в 2.
Пока d * d ≤ n: если d делит n, прибавить d, а также прибавить n / d, если оно отличается от d.
Перейти к следующему значению d.
Вернуть результат проверки, что total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Ловушки и крайние случаи

Приём с парами короткий, и каждая из его ошибок изменяет сумму ровно на один делитель.

Подсчёт самого n. Пара 1 × n добавляет n, и тогда сумма любого числа выглядит больше n. Начинай общую сумму с 1, а поиск — с 2.
Считать 1 совершенным числом. Если общая сумма начинается с 1, для входного значения 1 получается сравнение 1 == 1. Сумма его собственных делителей равна 0, поэтому обработай его до цикла.
Дважды добавлять квадратный корень. Для 16 собственные делители — это 1, 2, 4 и 8; их сумма равна 15. Если дважды добавить 4, получится 19.
Останавливать поиск на условии d * d < n. Так квадратный корень полностью пропускается, поэтому 4 для 16 никогда не будет учтён.
Брать верхнюю границу из квадратного корня с плавающей точкой. При одинарной точности или для чисел больше 2^53 при двойной точности корень полного квадрата может оказаться на единицу меньше и исключить делитель. Проверка d * d ≤ n выполняется с целыми числами, поэтому такой проблемы никогда не возникает.

Частые вопросы4

Какова временная сложность проверки того, является ли число совершенным?

Сбор пар делителей до √n занимает время O(√n) и пространство O(1). Для n = 10^8 это около 10^4 шагов. Проверка каждого кандидата до n / 2 имеет сложность O(n) — около 5 × 10^7 шагов для того же входного значения.

Сколько совершенных чисел меньше 10^8?

Пять: 6, 28, 496, 8128 и 33550336. Они быстро становятся всё реже. Следующее число, 8589869056, даже не помещается в 32-битное целое число.

Существуют ли нечётные совершенные числа?

Никто не знает. Все найденные на данный момент совершенные числа чётные. В ходе поисков были исключены нечётные совершенные числа меньше 10^1500, но нет доказательства, что их не может существовать. Ваша функция должна работать исходя из определения, а не из предположения, что входное значение чётное.

В чём разница между совершенными, избыточными и недостаточными числами?

Сравни сумму собственных делителей с числом. Если они равны, число совершенное, например 28. Если сумма больше, число избыточное, например 12, сумма делителей которого равна 16. Если сумма меньше, число недостаточное, как любое простое число, единственный собственный делитель которого — 1.

Python

def isPerfect(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

n = 28

Ожидается

true