Задача №114185. Делимость
Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от \(1\) до \(N\) в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять \(N = 10\), то получится \(4\) группы. Первая группа: 1. Вторая группа: 2, 7, 9. Третья группа: 3, 4, 10. Четвёртая группа: 5, 6, 8. Вы уже догадались, что, поскольку любое число делится на \(1\), одна группа всегда будет состоять только из числа \(1\), но в остальном подобное разбиение можно выполнить различными способами. От вас требуется определить минимальное число групп, на которое можно разбить все числа от 1 до \(N\) в соответствии с приведённым выше условием.
Программа получает на вход одно натуральное число \(N\), не превосходящее \(10^9\)
Программа должна вывести одно число – искомое минимальное количество групп.
Решение, правильно работающее только для случаев, когда \(N\) не превосходит 20, будет оцениваться в 20 баллов. Решение, правильно работающее только для случаев, когда \(N\) не превосходит \(10^3\) , будет оцениваться в 40 баллов. Решение, правильно работающее только для случаев, когда \(N\) не превосходит \(10^4\) , будет оцениваться в 60 баллов.
10
4