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