No.144

$i$ が素数として判定される確率を $p_i$ とする.

$i$ が素数のときは $p_i = 1$ である.

$i$ が $4$ のときは $2$ で篩にかけられない確率なので $p_4 = 1-p$ となり, $6$ のときは $2,3$ で篩にかけられない確率なので $p_6 = (1-p)^2$ である.

$i$ が $8$ のときは, $2,4$ で篩にかけられない確率であるが, $i$ によって篩にかけられないという事象を $A_i$ とすると,

$$p_8 = P(A_2 \cap A_4)$$

となる. 条件付き確率の公式より,

$$p_8 = P(A_2)P(A_4|A_2)$$

となり, $P(A_4 \lvert A_2)$ は $2$ で篩にかけられなかったという事象のもとでの $4$ で篩にかけられない事象の確率なので, これもやはり $1-p$ となる.

すなわち, $i$ が合成数のときは, $i$ の $1$ と自身を除く約数の数を $j$ とすると, $p_i = (1-p)^j$ となる.

個数の期待値は確率の合計である.

約数の数はエラトステネスの篩を改造して, $2$ のときは $4, 6, 8, \dots$ の項目をインクリメントする方法で求められる.