エラトステネスの篩を数式で表すと・・・？ - tsujimotterのノートブック

素数の一覧表を作るときに、一個一個の数を素数かどうか判定していくのもよいですが、もう少し効率的に行う方法があります。 その方法の一つが エラトステネスの篩（ふるい） です。 エラトステネスの篩は、情報系の大学生であればプログラミングの演習等で一度は実装したことがあるかと思いますが、実に「アルゴリズム的」なものです。説明の際は「手順」を説明されることが多く、私はこれを数式で表そうと考えたことがありませんでした。 ところが、Wikipediaを見ると、エラトステネスの篩はこんな数式で表せると書いてあります。 細かい定義は次のとおりですが、本文の中で順に説明していきます。 ： 以下の素数の個数 ： 以下のすべての素数を掛け合わせて得られる数 ：メビウス関数 ：ガウス記号（ を超えない最大の整数） ： は を割り切る こんな風に表せるのか！と驚いた一方で、これはいったいどういうことなんだろうとも思