Вам дано целое число n.
Найдите количество чисел от 1 до n, которые имеют четное количество делителей.
Входные данные
В первой строке одно целое число n (1≤n≤109).
Выходные данные
Выведите ответ.
Система оценки
Данная задача содержит 10 тестов. Каждый тест оценивается в :
1≤n≤1000. Тесты с номерами 1-6.
1≤n≤105. Тесты с номерами 7-8.
1≤n≤109. Тесты с номерами 9-10.
Примечание
В примере:
У числа 1 делители: 1. Количество 1 - нечетно.
У числа 2 делители: 1,2. Количество 2 - четно.
У числа 3 делители: 1,3. Количество 2 - четно.
У числа 4 делители: 1,2,4. Количество 3 - нечетно.
У числа 5 делители: 1,5. Количество 2 - четно.
У числа 6 делители: 1,2,3,6. Количество 4 - четно.
У числа 7 делители: 1,7. Количество 2 - четно.
У числа 8 делители: 1,2,4,8. Количество 4 - четно.
У числа 9 делители: 1,3,9. Количество 3 - нечетно.
У числа 10 делители: 1,2,5,10. Количество 4 - четно.
Примеры
входные данные
10
выходные данные
7
зачем решать олимпиаду если ничего не знаешь
Объяснение:
n = int(input())
a = 0
for i in range(1, n + 1):
for j in range(1, i + 1):
if i % j == 0:
a += 1
if a % 2 == 0:
print(i)
на набросок