練習問題1.4 - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

π(x)を与える一見すごそうな公式に見えるのだが、実は前問と同じく計算としては実用性のないものである。

nをkで割って n=k･m+r , 0≦r＜k と表しておく。 $\lfloor\frac{n}{k}\rfloor=m$ であるから、 $\lfloor\frac{n}{k}\rfloor \frac{k}{n}=\frac{mk}{n}=\frac{n-r}{n}$ よって

$\lfloor \lfloor\frac{n}{k}\rfloor \frac{k}{n}\rfloor=0$ ⇔ r≠0 ⇔ kはnを割り切らない

$\lfloor\lfloor\frac{n}{k}\rfloor \frac{k}{n}\rfloor=1$ ⇔ r=0 ⇔ kはnを割り切る

が成立する。よって $\sum_{k=2}^n \lfloor\lfloor\frac{n}{k}\rfloor \frac{k}{n}\rfloor$ = nの2以上の約数の数

であるから、和の部分はnが素数の時 1、nが素数でないときは ≧2 となるため、その逆数の整数部分をとると、nが素数の時 1、nが素数でないときは 0 となる。

結局、問題のnに関する和の部分はx以下の素数の数を数えており、すなわちπ(x)を与える。