Задача №114557. Делители

Вам дано целое число \(n\).

Найдите количество чисел от \(1\) до \(n\), которые имеют четное количество делителей.

Входные данные

В первой строке одно целое число \(n\) \((1 \le n \le 10^9)\).

Выходные данные

Выведите ответ.

Система оценки

Данная задача содержит \(10\) тестов. Каждый тест оценивается в \(10\) баллов:

  1. \(1 \le n \le 1000\). Тесты с номерами 1-6.

  2. \(1 \le n \le 10^5\). Тесты с номерами 7-8.

  3. \(1 \le n \le 10^9\). Тесты с номерами 9-10.

Примечание

В примере:

  1. У числа \(1\) делители: \(1\). Количество \(1\) - нечетно.
  2. У числа \(2\) делители: \(1, 2\). Количество \(2\) - четно.
  3. У числа \(3\) делители: \(1, 3\). Количество \(2\) - четно.
  4. У числа \(4\) делители: \(1, 2, 4\). Количество \(3\) - нечетно.
  5. У числа \(5\) делители: \(1, 5\). Количество \(2\) - четно.
  6. У числа \(6\) делители: \(1, 2, 3, 6\). Количество \(4\) - четно.
  7. У числа \(7\) делители: \(1, 7\). Количество \(2\) - четно.
  8. У числа \(8\) делители: \(1, 2, 4, 8\). Количество \(4\) - четно.
  9. У числа \(9\) делители: \(1, 3, 9\). Количество \(3\) - нечетно.
  10. У числа \(10\) делители: \(1, 2, 5, 10\). Количество \(4\) - четно.
Примеры
Входные данные
10
Выходные данные
7
Сдать: для сдачи задач необходимо войти в систему