PowerShell で Project Euler 7

問題

• 本家：Problem 7 - Project Euler
• 翻訳：Problem 7 - PukiWiki

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
10 001 番目の素数を求めよ.

エラトステネスの篩

10001 |
    ? {$_ -ge 1} |
    % {$count = 0} `
      {
        $maxCount = $_
        $upper = [Math]::Max(11, [Math]::Ceiling($_ * ([math]::log($_) + [math]::log([math]::log($_)))))
        $skip = New-Object System.Collections.BitArray ($upper - 1)
        foreach($p in 2..$upper)
        {
            if ($skip.Get($p - 2))
                {continue}

            $count++
            if ($count -eq $m)
                {return $p}

            for($i = $p * $p; $i -le $upper; $i += $p)
                {$skip.Set($i - 2, $true)}
        }
    }

エラトステネスの篩は１～Xに存在する素数を列挙するアルゴリズムで、使う場合は、上限Xを指定する必要がある。上記プログラムではピエール・デザルト先生の下記公式を使って上限を見積もっている。

• $\pi(n) < n (\ln n + \ln (\ln n))$
  • $n \ge 6$ のとき成り立つ
  • $\pi$ : 素数計数関数
  • $\ln$ : 自然対数

以上

素数計数関数に関する不等式の研究があることを初めて知った。