Решето Эратосфена - часть 2

Обозначим через

$\alpha _1$

свойство числа делиться на 2, через

$\alpha _2$

- свойство делимости на 3 и через

$\alpha _3$

- свойство делимости на 5. Тогда

$\alpha _1 \alpha _2$

означает, что число делится на 6,

$\alpha _1 \alpha _3$

означает, что оно делится на 10, и

$\alpha _2 \alpha _3$

- оно делится на 15. Наконец,

$\alpha _1 \alpha _2 \alpha _3$

означает, что число делится на 30. Надо найти, сколько чисел от 1 до 100 не делится ни на 2, ни на 3, ни на 5, то есть не обладает ни одним из свойств

$\alpha _1$

$\alpha _2$

$\alpha _3$

. По формуле 6.3 имеем

$N(\alpha _1' \alpha _2' \alpha _3')=100-N(\alpha _1 ) - N(\alpha _2 ) - N(\alpha _3 ) + N(\alpha _1 \alpha _2 ) + N(\alpha _1 \alpha _3 ) + N(\alpha _2 \alpha _3 ) - N(\alpha _1 \alpha _2 \alpha _3 ).$

Но чтобы найти, сколько чисел от 1 до

$N$

делится на

$n$

, надо разделить

$N$

на

$n$

и взять целую часть получившегося частного. Поэтому

$N(\alpha_1)=50,N(\alpha_2)=33,N(\alpha_3)=20,$

$N(\alpha_1\alpha_2)=16,N(\alpha_1\alpha_3)=10,N(\alpha_2\alpha_3)= 6,N(\alpha _1 \alpha \alpha _3 ) = 3,$

и значит,

$N(\alpha _1' \alpha _2' \alpha _3' ) = 32.$

Таким образом, 32 числа от 1 до 100 не делятся ни на 2, ни на 3, ни на 5. Эти числа и уцелеют после первых трех шагов процесса Эратосфена. Кроме них останутся сами числа 2, 3 и 5. Всего останется 35 чисел.

А из первой тысячи после первых трех шагов процесса Эратосфена останется 335 чисел. Это следует из того, что в этом случае

$N(\alpha _1 ) = 500,N(\alpha _2 ) = 333,N(\alpha _3 ) = 200,$

$N(\alpha _1 \alpha _2 ) = 166,N(\alpha _1 \alpha _3 ) = 100,N(\alpha _2 \alpha _3 ) =66,N(\alpha _1 \alpha _2 \alpha _3 ) = 33.$

Содержание Назад Вперед