ЕГЭ по информатике 25 задание. Поиск всех делителей (Оптимальный метод)

Если вы хоть раз решали задачи по математике или программированию, то точно сталкивались с вопросом:

👉 “Как найти все делители числа?”

На первый взгляд — просто. Но если число большое (например, миллион или миллиард), наивный способ может работать вечность.

Давайте разберёмся, как делать это правильно и быстро.

Самая очевидная идея — перебрать все числа от 1 до xxx и проверить:

делится ли x на d

Проблема:

если x=1000000, это уже миллион проверок.

Оптимальный алгоритм

Что получили:

• x=1 000 000 000
• было: 1 млрд операций
• стало: всего ~30 000

Проверка числа на простоту

Теперь можно легко понять:

👉 число простое, если у него нет делителей (кроме 1 и себя)

Факторизация (разложение на множители)

Используется, если в задаче нужно найти «простые делители» или их количество.

Суть метода: Мы последовательно делим число на потенциальные простые множители, начиная с 2, пока оно делится. Проверять
сами делители на простоту в цикле необязательно, так как составные делители (например, 4) «вымоются» более мелкими
простыми (например, 2) ранее.

Объяснение на доске

Пример:

100 → 2 → 50
50 → 2 → 25
25 → 5 → 5
5 → 5 → 1

Итого:

1 способ

2 способ

Пример задания

Нам нужны числа:

• больше 15 381 264
• которые раскладываются ровно на 3 простых множителя
• множители могут повторяться (например: 3 × 3 × 11)
• каждый множитель содержит ровно одну цифру "1"

Вспоминаем факторизацию

Из конспекта:

👉 мы умеем раскладывать число на простые множители

Условие "ровно 3 множителя"

После факторизации:

[2, 3, 11] → подходит
[2, 2, 3, 11] → НЕ подходит

👉 проверка:

len(divs) == 3

Условие "ровно одна цифра 1"

Примеры:

• 11 → подходит (две единицы ❌ → НЕ подходит!)
• 13 → подходит (одна "1")
• ❌ 101 → две "1"
• ❌ 7 → ноль "1"

👉 проверка:

str(d).count('1') == 1

ВАЖНЫЙ момент (частая ошибка учеников)

👉 Проверяем каждый множитель, а не число целиком!

Шаг 5. Перебор чисел

Идём по числам:

x = 15381265

И увеличиваем:

x += 1

Пока не найдём 5 подходящих.

🧠 Шаг 6. Алгоритм целиком

Идея:

1. Перебираем числа
2. Делаем факторизацию
3. Проверяем:ровно 3 множителя
   каждый содержит одну "1"
   
4. Запоминаем число
5. Выводим:число
   максимальный множитель
   

💻 Готовое решение (понятное для ученика)

Освоив эти приёмы, вы сможете решать задачи 25 задачи быстрее и увереннее.

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