Решето Эратосфена - часть 2
Обозначим через
свойство числа делиться на 2, через
- свойство делимости на 3 и через
- свойство делимости на 5. Тогда
означает, что число делится на 6,
означает, что оно делится на 10, и
- оно делится на 15. Наконец,
означает, что число делится на 30. Надо найти, сколько чисел от 1 до 100 не делится ни на 2, ни на 3, ни на 5, то есть не обладает ни одним из свойств
,
,
. По формуле 6.3 имеем
Но чтобы найти, сколько чисел от 1 до
делится на
, надо разделить
на
и взять целую часть получившегося частного. Поэтому
и значит,
Таким образом, 32 числа от 1 до 100 не делятся ни на 2, ни на 3, ни на 5. Эти числа и уцелеют после первых трех шагов процесса Эратосфена. Кроме них останутся сами числа 2, 3 и 5. Всего останется 35 чисел.
А из первой тысячи после первых трех шагов процесса Эратосфена останется 335 чисел. Это следует из того, что в этом случае
Содержание Назад Вперед