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

Legendreによる素数定理π(x)=o(x)の証明を再現する問題らしい。

まず、 $\phi(x,\quad \sqrt{x})$ であるが、 $\phi(x,\quad y)$ の定義から、『1≦n≦x で nの素因子がすべて $\sqrt{x}$ より大きいような n』の個数である。ところが、nが $\sqrt{x}$ より大きな素数のどれかに一致しない場合、nのその他の素因子は $\sqrt{x}$ より小さくなるため、条件を満たさなくなる。（ただし、1の素因子というものが存在しないため、n=1だけは例外として常に条件を満たしている。）
このことから、 $\phi(x,\quad \sqrt{x})=\pi(x)-\pi(\sqrt{x})+1$ が成立する。（最後の+1は、1という例外のためのカウントである。）

また、 $\phi(x,\quad \sqrt{x})$ にカウントされる条件を、
＃｛1≦n≦x で nがすべての $\sqrt{x}$ 以下の素数の倍数でないもの｝＝ x -　＃｛1≦n≦x で nが $\sqrt{x}$ 以下の素数の倍数であるもの｝
と言い換えると、
$\phi(x,\quad \sqrt{x})=\sum_{d\mid Q}\mu(d)\lfloor \frac{x}{d} \rfloor$
が成立している。（d=1のとき、 $\mu(1) \lfloor \frac{x}{1} \rfloor=x$ になることに注意。）□

$\phi(x,\quad y)$ を『1≦n≦x で nがy以下の素数の倍数でないようなもの』の個数と言い換えると、練習問題 1.10での経験から、 $\{q_i\}_{i=1}^n$ を $y$ 以下のすべての素数の集合とすると、(n=π(y)である。）

[tex:\phi(x,\quad y)=x-\sum_{q_i}^n \lfloor\frac{N}{q_i}\rfloor+\sum_{i