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

На питоне!

Question

Информатика

Людмилыч

18 февраля, 10:06

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

На питоне!

+1

Ответы (1)

Знаете ответ?

Артемий · Answer 1

Итак, нужно найти число групп, в каждой из которых ни одно из чисел не делит все остальные.

Строим группы так:

(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 = 1

k = 0

while t < = n:

t * = 2

k + = 1

print (k)