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

■■■問題■■■

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

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

候補リストに含まれる最小の数をxとする。
xを素数リストへ移動し、2x,3x,4x,・・・ を候補リストから削除する。

候補リストが空になったとき、素数リストに含まれる数が素数である。

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

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

■■■入力■■■

N p

2 <= N <= 100万
0 <= p <= 1
pは小数第5位まで与えられる。

■■■出力■■■

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

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("10 1.00000");
            //4
            //しっかり者のゆきこちゃんは、下線部の処理を必ず行う。
            //このとき、アルゴリズムは正しく実行され、2,3,5,7が素数として列挙される。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 0.00000");
            //9
            //超うっかり者のゆきこちゃんは、下線部の処理をまったく行わない。
            //このとき、2から10までのすべての数が素数として列挙される。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 0.50000");
            //5.75
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] wkArr = InputList[0].Split(' ');

        int N = int.Parse(wkArr[0]);
        double p = double.Parse(wkArr[1]);

        //自分以外の約数の個数の配列
        int[] YakusuuCntArr = new int[N + 1];
        for (int I = 2; I * 2 <= N; I++) {
            for (int J = I * 2; J <= N; J += I) {
                YakusuuCntArr[J]++;
            }
        }

        for (int I = 2; I <= N; I++) {
            Console.WriteLine("YakusuuCntArr[{0}]={1}", I, YakusuuCntArr[I]);
        }

        //期待値の加法性を使って、期待値を計算
        double Answer = 0;
        for (int I = 2; I <= N; I++) {
            if (YakusuuCntArr[I] == 0) Answer++;
            else {
                //確率の乗法定理
                Answer += Math.Pow(1 - p, YakusuuCntArr[I]);
            }
        }
        Console.WriteLine(Answer);
    }
}

デバッグ情報付の実行結果

YakusuuCntArr[2]=0
YakusuuCntArr[3]=0
YakusuuCntArr[4]=1
YakusuuCntArr[5]=0
YakusuuCntArr[6]=2
YakusuuCntArr[7]=0
YakusuuCntArr[8]=2
YakusuuCntArr[9]=1
YakusuuCntArr[10]=2
4

解説

素数でない数は、自分以外の全ての約数で、ふるいを回避できれば、表示されます。
この確率を、確率の乗法定理で求め、期待値の加法性を使ってます。