alg11
11. Докажите формулу для подсчета количества делителей натурального числа.
Решение.
Все делители, на которые данное число делится нацело, можно получить из разложения числа на простые множители.
Нахождение всех делителей числа выполняется следующим образом:
1) Сначала нужно разложить данное число на простые множители.
2) Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
3) Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
4) В конце добавляем в качестве делителя единицу.
Пример
Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:
Выписываем (без повторов) каждый полученный простой множитель — это 2 и 5.
Далее находим всевозможные произведения всех полученных простых множителей между собой:
2 · 2 = 4,
2 · 2 · 2 = 8,
2 · 5 = 10,
2 · 2 · 5 = 20,
2 · 2 · 2 · 5 = 40.
Добавляем в качестве делителя 1.
В итоге получаем все делители, на которые число 40 делится без остатка:
1, 2, 4, 5, 8, 10, 20, 40.
Других делителей у числа 40 нет.