練習問題1.3

素数全書 演習問題

和の中でm=nの時とm=1の時はどちらも\lfloor{\frac{n}{m}}\rfloor-\lfloor\frac{n-1}{m}\rfloor=1となるので、それ以外の項の和が 0 かどうかで素数判定できるという等式である。

n:素数でない⇒ ∃p,q＞1 (n=p・q) ⇒ \lfloor\frac{n}{p}\rfloor-\lfloor\frac{n-1}{p}\rfloor=q-(q-1)=1

であるから素数でないなら和は2でない。つまり 問題の和=2 ⇒ n:素数


逆に 1＜m＜n かつ \lfloor\frac{n}{m}\rfloor-\lfloor\frac{n-1}{m}\rfloor=1なる m が存在したとする。

nをmで割って n=k･m+r , 0≦r＜m と表しておく。

このとき、r＞0 ならば \lfloor \frac{n}{m} \rfloor-\lfloor \frac{n-1}{m} \rfloor =\lfloor k+\frac{r}{m} \rfloor-\lfloor k+\frac{r-1}{m} \rfloor=k-k=0となって仮定に反する。よって r=0 となるが、これはnがmで割り切れることになり、nは素数でない。

よって n:素数 ⇒ 問題の和=2 と逆も成立する。

もちろん素数判定法としては、2から順番に割ってみて調べる計算と同じようなもので実用性はない。