Посчитать количество делителей числа

• Как найти количество делителей
• Как найти неизвестный множитель
• Как разделить меньшее число на большее

• — таблица простых чисел;
• — признаки делимости чисел;
• — калькулятор.

Например, количество простых делителей числа 364 найдите таким образом:

Получите числа 2, 2, 7, 13, которые являются простыми натуральными делителями числа 364. Их количество равно 3 (если считать повторяющиеся делители за один).

Все делители числа

Все делители, на которые данное число делится нацело можно получить из разложения числа на простые множители.

Нахождение всех делителей числа выполняется следующим образом:

1. Сначала нужно разложить данное число на простые множители.
2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
4. В конце добавляем в качестве делителя единицу.

Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:

Выписываем (без повторов) каждый полученный простой множитель – это 2 и 5.

Далее находим всевозможные произведения всех полученных простых множителей между собой:

Добавляем в качестве делителя 1. В итоге получаем все делители, на которые число 40 делится без остатка:

1, 2, 4, 5, 8, 10, 20, 40

Других делителей у числа 40 нет.

Калькулятор нахождения всех делителей

Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку "Вычислить".

Никак не могу справиться с задачей, заданной в ВУЗе — пишет, что превышен лимит времени. Я вообще не понимаю как тут её решить. Вот сама задача:

А вот мой код:

3 ответа 3

Ох, побьют меня сейчас за неспортивное поведение. 🙁 Но задачка интересная, хотелось бы узнать — все же нет ли какого-то способа побыстрее, чем перебор.

У меня — просто разложение на простые множители и произведение увеличенных на 1 степеней.

Update
Немного ускорил — не считаем все корни, если уже перевалили нужное число.

UPD: Я бы посоветовал вам не объявлять переменные для цикла for вне самого цикла, если уж не используете значение i после его завершения. А так же делайте отступы между арифм. операциями и всем остальным

Давайте научимся за линейное время находить все простые числа, заодно составим табличку для факторизации числа за кол-во чисел в факторизации, таким образом мы получим решение за O(N * const)