Петров
5 год назад
Сегодня в школе на уроке математики проходят делимость. Чтобы продемонстрировать свойства делимости, учитель выписал на доске все целые числа от 1 до N в несколько групп, при этом если одно число делится на другое, то они обязательно оказались в разных группах. Например, если взять N = 10, то получится 4 группы. Первая группа: 1. Вторая группа: 2, 7, 9. Третья группа: 3, 4, 10. Четвёртая группа: 5, 6, 8. Вы уже догадались, что, поскольку любое число делится на 1, одна группа всегда будет состоять только из числа 1, но в остальном подобное разбиение можно выполнить различными способами. От вас требуется определить минимальное число групп, на которое можно разбить все числа от 1 до N в соответствии с приведённым выше условием. Программа получает на вход одно натуральное число N, не превосходящее 109, и должна вывести одно число – искомое минимальное количество групп.
На питоне!
ОТВЕТЫ
Бухвостов
Aug 12, 2019
Итак, нужно найти число групп, в каждой из которых ни одно из чисел не делит все остальные.
Строим группы так:
(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) gt; N
По построению явно во всех группах ни одно число не делится на другое. Осталось проверить, что получено минимальное число групп.
Это очевидно: числа 1, 2, 4, ..., 2^(k-1) должны быть в разных группах.
Решение:
n = int(input())
t = 1
k = 0
while t lt;= n:
t *= 2
k += 1
print(k)
Строим группы так:
(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) gt; N
По построению явно во всех группах ни одно число не делится на другое. Осталось проверить, что получено минимальное число групп.
Это очевидно: числа 1, 2, 4, ..., 2^(k-1) должны быть в разных группах.
Решение:
n = int(input())
t = 1
k = 0
while t lt;= n:
t *= 2
k += 1
print(k)
85
Смежные вопросы:
