Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы. Первая группа: 1. Вторая группа: 2, 7, 9. Третья группа: 3, 4, 10. Четвёртая группа: 5, 6, 8. Вы уже догадались, что, поскольку любое число делится на 1, одна группа всегда будет состоять только из числа 1, но в остальном подобное разбиение можно выполнить различными способами. От вас требуется определить минимальное число групп, на которое можно разбить все числа от 1 до N в соответствии с приведённым выше условием. Программа получает на вход одно натуральное число N, не превосходящее 109, и должна вывести одно число – искомое минимальное количество групп.
На питоне!

Итак, нужно найти число групп, в каждой из которых ни одно из чисел не делит все остальные.Строим группы так:(1) - 1(2) - 2, 3, 5, 7, 11, 13... - все простые(3) - 4, 6, 9, 10, 14, 15... - произведения двух простых ...(k) - произведения (k - 1) простыхИ так пока не кончатся все числа. Поскольку в каждой группе наименьшее число 2^(k - 1), то k - минимальное, для которого 2^(k - 1) > NПо построению явно во всех группах ни одно число не делится на другое. Осталось проверить, что получено минимальное число групп.Это очевидно: числа 1, 2, 4, ..., 2^(k-1) должны быть в разных группах.Решение:n = int(input())t = 1k = 0while t <= n:    t *= 2    k += 1print(k)