No.144 Sieve of Eratosthenes, the Leaky One
タグ : / 解いたユーザー数 381
作問者 :
sugim48
Problem Statement
The "Sieve of Eratosthenes" is a classic algorithm that enumerates the primes less than or equal to a given natural number $N$.
The algorithm is shown below.
First, prepare a "candidate list" consisting of the integers from $2$ to $N$, and an empty "prime list".
Repeat the following step until the candidate list becomes empty.
候補リストに含まれる最小の数を $x$ とする。 $x$ を素数リストへ移動し、2x, 3x, 4x, ... を候補リストから削除する。When the candidate list becomes empty, the numbers in the prime list are the primes.
Yukiko is going to run this algorithm to enumerate the primes less than or equal to $N$.
However, being careless, Yukiko may skip the underlined operation entirely in some steps.
That is, after moving $x$ to the prime list, she immediately proceeds to the next step.
Because of this, the numbers enumerated as primes may not be correct.
Now, suppose that in each step the underlined operation is performed with probability $p$.
Find the expected value of the count of numbers enumerated as primes.
Input
$N$ $p$
$2\leq N\leq 10^6$
$0\leq p\leq 1$
$p$ is given to $5$ decimal places.
Output
Output the expected value of the count of numbers enumerated as primes.
Your answer is accepted if the absolute error or the relative error is at most $10^{-6}$.
Sample
Sample 1
Input
10 1.00000
Output
4
A careful Yukiko always performs the underlined operation.
In this case, the algorithm runs correctly, and $2,3,5,7$ are enumerated as primes.
Sample 2
Input
10 0.00000
Output
9
An extremely careless Yukiko never performs the underlined operation.
In this case, all the numbers from $2$ to $10$ are enumerated as primes.
Sample 3
Input
10 0.50000
Output
5.75
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。