Комбинаторные алгоритмы для программистов



             

Решето Эратосфена - часть 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.




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