Ctrl K

Не ровно три делителя

Средняя
Даны два натуральных числа low и high. Посчитайте, сколько чисел на отрезке от low до high включительно имеют количество натуральных делителей, **отличное** от трёх (единица и само число тоже считаются делителями). Перебрать все числа и делители не получится: отрезок может быть длиной почти в миллиард.
Пример 1
low=1, high=10 → 8

Ровно три делителя только у 4 (1, 2, 4) и у 9 (1, 3, 9). Остальные 8 чисел подходят.

Пример 2
low=20, high=30 → 10

Из 11 чисел ровно три делителя только у 25 (1, 5, 25).

Ограничения
  • 1 ≤ low ≤ high ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПростые числа до границы СредняяРамки одной формы СредняяОтрезки на графике СредняяКуски с общим делителем СредняяОтрезки с заданным НОД Средняя
загружаем Python…
Вход
low=1, high=10
Ожидается
8

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 79 тестов на сервере, включая скрытые.