No.144 エラトステネスのざる

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下
タグ : / 解いたユーザー数 144
作問者 : sugim48sugim48

18 ProblemId : 242 / 出題時の順位表

問題文

「エラトステネスのふるい」は、与えられた自然数 $N$ 以下の素数を列挙する古典的アルゴリズムである。
以下にそのアルゴリズムを示す。

まず、$2$ から $N$ までの整数からなる「候補リスト」と、空の「素数リスト」を用意する。
候補リストが空になるまで、次のステップを繰り返す。

候補リストに含まれる最小の数を $x$ とする。
$x$ を素数リストへ移動し、2x, 3x, 4x, ... を候補リストから削除する
候補リストが空になったとき、素数リストに含まれる数が素数である。

ゆきこちゃんはこのアルゴリズムを実行し、$N$ 以下の素数を列挙しようとしている。
ただし、うっかり者のゆきこちゃんは、ステップによっては下線部の処理を丸々飛ばしてしまう。
つまり、$x$ を素数リストへ移動した後、すぐに次のステップへ移ってしまう。
このため、素数として列挙される数は正しくない可能性がある。

さて、各ステップで下線部の処理が行われる確率が $p$ であるとする。
このとき、素数として列挙される数の個数の期待値を求めよ。

入力

$N$ $p$

$2\leq N\leq 10^6$
$0\leq p\leq 1$
$p$ は小数第 $5$ 位まで与えられる。

出力

素数として列挙される数の個数の期待値を出力せよ。
絶対誤差または相対誤差が $10^{-6}$ 以下ならば許容される。

サンプル

サンプル1
入力
10 1.00000
出力
4

しっかり者のゆきこちゃんは、下線部の処理を必ず行う。
このとき、アルゴリズムは正しく実行され、$2,3,5,7$ が素数として列挙される。

サンプル2
入力
10 0.00000
出力
9

超うっかり者のゆきこちゃんは、下線部の処理をまったく行わない。
このとき、$2$ から $10$ までのすべての数が素数として列挙される。

サンプル3
入力
10 0.50000
出力
5.75

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。