Ctrl K

Сколько ламп останется гореть

Средняя
В коридоре стоят count выключенных ламп, пронумерованных от 1 до count. Проводится count раундов: в раунде k переключается каждая лампа, номер которой делится на k (включённая гаснет, выключенная загорается). Так, в первом раунде включаются все лампы, а в последнем переключается только лампа с номером count. Верните, сколько ламп будет гореть после всех раундов.
Пример 1
count=5 → 2

После раунда 1 горят все пять. Раунд 2 гасит 2 и 4, раунд 3 гасит 3, раунд 4 снова включает 4, раунд 5 гасит 5. Горят лампы 1 и 4.

Пример 2
count=0 → 0

Ламп нет — гореть нечему.

Пример 3
count=10 → 3
Ограничения
  • 0 ≤ count ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиТри камня в ряд СредняяПоследний зритель на своём месте СредняяБери из любой кучки СредняяЗеркально во всех системах СредняяИЛИ всех сумм подмножеств Средняя
загружаем Python…
Вход
count=5
Ожидается
2

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