素数に関する評価

1. 概要

競技プログラミングの学習をしていると，次のような結果を目にすることがあると思います．

• $N$ 以下の素数の個数は $\displaystyle \frac{N}{\log N}$ 程度である（素数定理）．
• $N$ 以下の素数の逆数の総和 $\displaystyle \sum_{p\leq N}\frac{1}{p}$ は $\log\log N$ 程度である（Mertens の定理）．

なお，本記事では $p$ と書けば素数を表すものとし，$N$ 以下の素数に対する和を $\displaystyle \sum _ {p\leq N} \frac{1}{p}$ のように $\displaystyle \sum _ {p\leq N}$ で表します（総積 $\displaystyle \prod_{p\leq N}$ も同様です）．

このような素数に関する評価は，証明に複素解析学などの高度な数学を必要とする場合があるため，競技プログラミングでは証明せずに結果だけが紹介されることが多いです．

一方で，定数倍の評価を妥協すれば，高校数学レベルでも十分証明できて，また競技プログラミングにおいてはそれで十分なことも多いです．そこで本記事では，高校数学レベルで素数に関するさまざまな和や積に関する評価を証明することを目標とします．

例えば素数定理は，$N$ 以下の素数の個数が $(1+o(1))\cdot \dfrac{N}{\log N}$ であるというものですが，本記事では $\Theta\left(\dfrac{N}{\log N}\right)$ であるというより弱い結果を証明します（これが上に述べた「定数倍に関する評価を妥協する」ということです）．

本記事では，競技プログラミングの解説で見かけることのある評価を複数証明しているため，記事は少し長く，数式が多いものとなっています．ただし，これらを証明する上でのアイデアとしては 3 節の素数の個数に関する部分が主で，4 節以降の証明は難しいアイデアを必要としない地道な計算からなるものが多いです．

式変形を追うのが苦手な方は，計算の細部は確認せずに，3 節についてどのような仕組みで素数の個数が上下から評価されているのかの理解に集中して学習すると楽しめると思います．

2. 前提知識

$p$ 進付値の記号を用います．素数の性質 【定義 7】 を参照してください．

また，Landau の記号（$\mathrm{O}, \Theta, \mathrm{o}$）を用います．

4 節では積分を用いる部分があります（高校数学レベルです）．

3. 素数の個数

3.1. 本節で証明する定理

【定義 1】
実数 $x$ に対して，$x$ 以下の素数の個数を $\pi(x)$ と書く．$\pi$ を素数計数関数（prime-counting function）という．

整数論では $\pi(x)$ について積分などの式変形をすることも多いため，定義域を実数とすることが多いですが，もちろん $\pi(x)=\pi(\lfloor x\rfloor)$ であり，重要なのは $x$ が整数の場合です．例えば次のような値となります．

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\pi(x)$	$0$	$1$	$2$	$2$	$3$	$3$	$4$	$4$	$4$	$4$

$x=10 ^ n$ の場合には，次のような値が知られています．

$x$	$\pi(x)$
$10$	$4$
$10 ^ 2$	$25$
$10 ^ 3$	$168$
$10 ^ 4$	$1229$
$10 ^ 5$	$9592$
$10 ^ 6$	$78498$
$10 ^ 7$	$664579$
$10 ^ 8$	$5761455$
$10 ^ 9$	$50847534$
$10 ^ {10}$	$455052511$

ここでは，次の定理を目標とします．

【定理 2】
$$ \left(\log 2 + \mathrm{o}(1)\right) \cdot \frac{N}{\log N} \leq \pi(N)\leq \left(2\log 2 + \mathrm{o}(1)\right)\cdot \frac{N}{\log N}. $$

$\mathrm{o}$ 記法に関する注意

このように $\mathrm{o}$ 記法が式の一部の項に現れる式は，あまり見たことがない方もいるかもしれません．この場合には $\mathrm{o}$ 記法を使わずに定式化すると，次のようになります．

$\lim _ {N \to \infty} f(N)=0$，$\lim_{N \to \infty} g(N)=0$ となる関数 $f,g$ が存在して次が成り立つ：

$$ \left( \log 2 + f (N)\right) \cdot \frac{N}{\log N} \leq \pi(N) \leq \left( 2\log 2 + g (N) \right)\cdot \frac{N}{\log N} $$

特に，$\displaystyle \pi(N)=\Theta\left(\frac{N}{\log N}\right)$ である．

3.2. 準備

【補題 3】

$p$ を素数，$N$ を正整数とする．$M=\lceil N/2\rceil$ とする．このとき次が成り立つ．

1. $\displaystyle \frac{2 ^ N}{N+1}\leq \binom{N}{M}\leq 2 ^ N$．
2. $\displaystyle v_p(N!)=\sum_{k=1}^{\infty}\left\lfloor \frac{N}{p ^ k}\right\rfloor$．（Legendre の公式）
3. $\displaystyle v_p\left(\binom{N}{M}\right)\leq \log_p N$ が成り立つ．
4. $M < p\leq N$ ならば $\displaystyle v_p\left(\binom{N}{M}\right)=1$ が成り立つ．

1 を示します．$\displaystyle \sum_{i=0} ^ N \binom{N}{i}=2 ^ N$ が成り立ちます．また，$\displaystyle \binom{N}{i}$ のうちで最大のものが $\displaystyle \binom{N}{M}$ です（例えば隣接する $2$ つの $\displaystyle \binom{N}{i}$ の比を考えることで証明できます）． 総和が $2 ^ N$ となっている $N+1$ 個の正整数について，その最大のものが $\dfrac{2 ^ N}{N+1}$ 以上 $2 ^ N$ 以下であることから，1 が成り立ちます．

2 を示します．$\displaystyle v _ p(N!) = \sum _ {n=1} ^ N v_p(n)$ です．さらに $\displaystyle v_p(n)=\sum_{k=1}^{\infty} [\, p ^ k\mid n\,]$ です．ただし，$[\, p ^ k\mid n\,]$ は $n$ が $p ^ k$ の倍数ならば $1$，そうでなければ $0$ を表す記号です（Iverson bracket による表記）．したがって，

$$v_p(N!) = \sum _ {n=1} ^ N v_p(n) = \sum _ {n=1} ^ N \sum _ {k=1} ^ {\infty} [\, p ^ k\mid n \,] = \sum _ {k=1} ^ {\infty} \sum _ {n=1} ^ N [\, p ^ k\mid n\,]$$

となりますが，$\displaystyle \sum _ {n=1} ^ N [ \, p ^ k \mid n\, ]$ は $1$ 以上 $N$ 以下の $p ^ k$ の倍数の個数なので，$\left\lfloor \dfrac{N}{p ^ k}\right\rfloor$ です．以上により示されました．

3 を示します．$\displaystyle \binom{N}{M}=\frac{N!}{M!(N-M)!}$ と 2 で示したことより

$$ v_p \left( \binom{N}{M} \right) = \sum _ {k=1} ^ {\infty} \left(\left\lfloor \frac{N}{p ^ k}\right\rfloor-\left\lfloor \frac{M}{p ^ k}\right\rfloor-\left\lfloor \frac{N-M}{p ^ k}\right\rfloor\right) $$

が成り立ちます．ここで $1\leq k\leq \log_p N$ について，

$$\left\lfloor \frac{N}{p ^ k}\right\rfloor-\left\lfloor \frac{M}{p ^ k}\right\rfloor-\left\lfloor \frac{N-M}{p ^ k}\right\rfloor\leq 1$$

です．これは実数 $a,b$ について $\lfloor a+b\rfloor - \lfloor a\rfloor - \lfloor b\rfloor \leq 1$ であることから成り立ちます．$\log_p N < k$ については $0$ となることは明らかです．したがって 3 が示されました．

4 を示します．仮定より $p\leq N < 2p$ なので，$v_p(N!)=1$ です．また $v _ p ( M !) = v_p ( (N-M) ! ) = 0$ なので，$\displaystyle \binom{N}{M}=\frac{N!}{M!(N-M)!}$ より $\displaystyle v_p\left( \binom{N}{M} \right)=1$ となります． $\blacksquare$

3.3. 下界の証明

$M=\lceil N/2\rceil$ とすると 【補題 3】 1, 3 より，次が成り立ちます．

$$ \frac{2 ^ N}{N+1} \leq \binom{N}{M} \leq \prod _ {p\leq N} p ^ {\log_p N} \leq \prod _ {p\leq N} N \leq N ^ {\pi(N)}. $$

両辺の対数をとることで

$$N\log 2 - \log(N+1)\leq \pi(N)\cdot \log N$$

が成り立ち，これを整理することで定理の下界が得られます． $\blacksquare$

3.4. 上界の証明

$M=\lceil N/2\rceil$ とすると 【補題 3】 1, 4 より，次が成り立ちます．

$$\prod_{M<p\leq N}p\leq \binom{N}{M}\leq 2 ^ N$$

さらに左辺は $M ^ {\pi(N)-\pi(M)}$ 以上なので，$M ^ {\pi(N)-\pi(M)}\leq 2 ^ N$ より

$$\pi(N)\leq \pi(M) + \frac{N\log 2}{\log M}$$

が成り立ちます．$N_i=\left\lceil\frac{N}{2 ^ i}\right\rceil$ とおき，$N$ を $N_i$ としてこの式を使うと

$$ \pi(N _ i) \leq \pi(N _ {i+1}) + \frac{N _ i \log 2}{\log N _ {i+1}} $$

となります．正整数 $K$ を適当にとり，$0\leq i\leq K-1$ について足せば

$$ \pi(N) \leq \pi(N _ K) + \sum _ {i=0} ^ {K-1} \frac{N _ i\log 2}{\log N _ {i+1}} $$

となります．$K=2\lceil \log_2\log_2 N\rceil$ ととると，$2 ^ K \geq (\log_2 N) ^ 2$ より

$$ \pi(N_K)\leq N_K \leq 1 + \frac{N}{2 ^ K} = \frac{N}{\log N}\cdot \mathrm{o}(1) $$

です．また，この範囲で

$$ \frac{N_i}{\log N_{i+1}} = \frac{N / 2 ^ i}{\log (N / 2 ^ {i+1})}\cdot (1 + \mathrm{o}(1))=\frac{1}{2 ^ i}\frac{N}{\log N}\cdot (1 + \mathrm{o}(1)) $$

となるので，$\sum _ {i=0} ^ {K-1}\dfrac{1}{2 ^ i}\leq 2$ と合わせて目的の不等式

$$\pi(N)\leq \frac{N}{\log N}\cdot (2\log 2 + \mathrm{o}(1))$$

が得られます． $\blacksquare$

4. 素数に関するさまざまな評価

【定理 2】 から素数に関するさまざまな評価が示されます．以下で述べる定理も 【定理 2】 のように，証明を辿れば $\log 2$ などの定数を用いて上下から評価できますが，ここではそのような定数倍の議論は省略します．

4.1. $N$ 番目の素数

【定理 4】
昇順で $N$ 番目の素数は $\Theta(N\log N)$ である．

昇順で $N$ 番目の素数を $p_N$ とすると，まず 【定理 2】 から十分大きな正整数 $N$ について $N\leq p_N\leq N ^ 2$ が成り立ちます．したがって $\log N \leq \log p_N \leq 2\log N$ なので，

$$ \frac{p_N}{\log p_N}=\Theta\left(\frac{p_N}{\log N}\right) $$

となります．このことと，

$$ N=\pi(p_N)=\Theta\left(\frac{p_N}{\log p_N}\right) $$

から定理が成り立ちます．

4.2. 素数の逆数和

【定理 5】
$$\sum_{p\leq N}\frac{1}{p}=\Theta(\log \log N).$$

正整数 $x$ に対して

$$ \pi(x)-\pi(x-1)=\begin{cases}0 & (\text{$x$ は素数ではない}) \\ 1 & (\text{$x$ は素数})\end{cases} $$

であることから，この和は $\pi(x)$ を使って次のように表すことができます．

$$ \sum _ {x=2} ^ {N} \frac{\pi(x)-\pi(x-1)}{x} = \frac{\pi(N)}{N} + \sum _ {x=2} ^ {N-1} \pi(x) \cdot \left(\frac{1}{x}-\frac{1}{x+1}\right). $$

$\dfrac{\pi(N)}{N}$ は $0$ 以上 $1$ 以下なので，【定理 2】 より次を示せば十分です．

$$ \sum_{x=2}^{N-1}\frac{x}{\log x}\cdot \left(\frac{1}{x}-\frac{1}{x+1}\right)=\log\log N + \mathrm{O}(1). $$

これは，以下のことから示されます．

$$ \begin{aligned} &\sum_{x=2} ^ {N-1} \frac{x}{\log x} \cdot \left(\frac{1}{x} - \frac{1}{x+1}\right) = \sum _ {x=2} ^ {N-1} \frac{1}{x\log x} + \mathrm{O}(1), \\ &\sum _ {x=2} ^ {N-1} \frac{1}{x\log x} = \int _ 2 ^ N \frac{1}{x\log x} dx + \mathrm{O}(1), \\ &\int _ 2 ^ N\frac{1}{x\log x}dx = \log\log N + \mathrm{O}(1).\end{aligned} $$

それぞれは高校数学レベルの計算なので，詳細は省略します． $\blacksquare$

4.3. 素数の総積

【定理 6】
$$\sum_{p\leq N}\log p=\Theta(N).$$

第一 Chebyshev 関数

$\theta(x)=\sum_{p\leq x}\log p$ は第一 Chebyshev 関数と呼ばれ，素数分布に関する議論において頻出の関数です．

素数の総積との関係

$X_N = \prod_{p\leq N}p$ とすると，定理の左辺は $\log X_N$ です．このことから，【定理 6】 は素数の総積を評価しているものといえます．

定理は，$1 < A\leq B$ であるような定数 $A, B$ が存在して，$A^N\leq X_N\leq B^N$ が成り立つこととして言い換えることもできます．

4.2 節の議論と同様に，この和は $\pi(x)$ を使って次のように表すことができます．

$$ \sum_{x=2} ^ {N}(\pi(x)-\pi(x-1)) \log x = \pi(N)\log N + \sum _ {x=2} ^ {N-1} \pi(x) \cdot \left(\log x - \log(x+1)\right). $$

【定理 2】 より，$\pi(N)\log N=\Theta(N)$ であり，また $x\to \infty$ の極限について

$$\frac{x}{\log x}\cdot\left(\log x-\log(x+1)\right)=\frac{-x\log(1+1/x)}{\log x}\to 0$$

となる（$x\log (1+1/x)\to 1$ となることから）ので，定理の主張が得られます． $\blacksquare$

補足説明

最後の推論では，次が用いられています：実数列 $\lbrace a_n \rbrace$ について $a_n\to 0$ が成り立つならば $\sum_{n=2}^{N-1}a_n=\mathrm{o}(N)$．この事実をここで証明します．

正実数 $\varepsilon$ を任意にとると，仮定よりある正整数 $M$ に対して，$n > M\implies |a_n|<\varepsilon$ となります．したがって $C=\sum_{n=2}^M |a_n|$ とすれば，$N\geq M$ について $\sum_{n=2}^{N-1}|a_n| \leq C + (N-1-M)\varepsilon$ となります．これより十分大きなすべての $N$ について $\sum_{n=2}^{N-1}|a_n|\leq 2N\varepsilon$ が成り立ちます．

$\varepsilon$ は任意なので $\sum_{n=2}^{N-1}a_n=\mathrm{o}(N)$ となります．

4.4. 最小公倍数

【定理 7】
$$\log\left(\mathrm{lcm}(1,2,\ldots,N)\right)=\sum_{p\leq N}\lfloor \log_p N\rfloor \log p=\Theta(N).$$

第二 Chebyshev 関数

$\psi(x) = \sum_{p\leq x} \lfloor \log_p x \rfloor \log p$ は第二 Chebyshev 関数と呼ばれます．

直接証明することもできますが，ここでは 【定理 6】 との比較によって証明しておきましょう．

$$ \sum _ {p\leq N} \lfloor \log_p N \rfloor \cdot \log p =\sum _ {p\leq N}\log p + \sum _ {p\leq N} \left(\lfloor \log_p N \rfloor - 1\right) \log p $$

となるので，$\sum_{p\leq N}(\lfloor\log_p N\rfloor-1) \log p=\mathrm{o}(N)$ であることを示せばよいです．

$p$ について足す値が $0$ でないのは $p\leq \sqrt{N}$ の場合に限られ，また $\lfloor\log_p N\rfloor-1\leq \log_2N$ です．

$$ \sum _ {p\leq N}(\lfloor\log _ p N\rfloor - 1) \log p \leq \sum _ {p\leq\sqrt{N}} \log _ 2N\cdot \log p\leq \sqrt{N}\log _ 2N\cdot \log N=\mathrm{o}(N) $$

となり示されました． $\blacksquare$

4.5. 素因数の個数

【定義 8】

$n$ を正整数とするとき，その相異なる素因数の個数を $\omega(n)$ と書く．

小さな $n$ に対する値は次のようになります．

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\omega(n)$	$0$	$1$	$1$	$1$	$1$	$2$	$1$	$1$	$1$	$2$

$p$ が素数のとき，$\omega(p)=1$ が成り立ちます．$N$ の大きさに対して $\omega(N)$ を下から評価する問題については，これ以上の評価はできません．そこで上界について考えます．

【定理 9】
$$ \omega(N) = \mathrm{O}\left(\frac{\log N}{\log\log N}\right) $$

$K=\omega(N)$ とし，$M=p_K$ を昇順で $K$ 番目の素数とします．すると $\prod_{p\leq M}p\leq N$ が成り立ちます．

両辺の対数をとって 【定理 6】 を使うことで

$$ M = \mathrm{O}(\log N) $$

が分かります．さらに，$K\leq \pi(M)$ なので 【定理 2】 より

$$ \omega(N) = K = \mathrm{O}\left(\frac{M}{\log M}\right) $$

が成り立ちます．これらを合わせると定理が得られます．

4.6. Euler の totient 関数

$N$ を正整数とするとき，$0$ 以上 $N-1$ 以下の整数のうちで $N$ と互いに素なものの個数を $\varphi(N)$ と書き，$\varphi$ を Euler の totient 関数というのでした（原始根 【定義 5】）．

$N$ の相異なる素因数を $p_1,p_2,\ldots,p_K$ とするとき，

$$ \varphi(N) = N \prod _ {i=1} ^ K \left(1-\frac{1}{p_i}\right) $$

が成り立ちます．

【定理 10】
$$\frac{N}{\varphi(N)}=(\log \log N)^{\mathrm{O}(1)}.$$

$K=\omega(N)$ とし，$M=p_K$ を昇順で $K$ 番目の素数とします．すると，

$$ \frac{N}{\varphi(N)}\leq \prod_{p\leq M}\left(1-\frac{1}{p}\right)^{-1} $$

が成り立ちます．ここで右辺の対数は

$$ \sum_{p\leq M}-\log\left(1-\frac{1}{p}\right) $$

となりますが，$x\to 0$ のときに $\log(1+x)=\mathrm{O}(x)$ であることと 【定理 5】 からこれは $\mathrm{O}(\log \log M)$ となります．

したがって

$$ \frac{N}{\varphi(N)}=\exp\left(\mathrm{O}(\log\log M)\right)=(\log M)^{\mathrm{O}(1)} $$

です．あとは $M=p_K$ より $M=\Theta(K\log K)$ であることと，$K=\omega(N)=\mathrm{O}\left(\dfrac{\log N}{\log\log N}\right)$ であることから式を整理すると，定理の主張が得られます． $\blacksquare$

5. より厳密な評価

本記事のこれまでの部分では，高校レベルの数学だけで厳密に証明することを重視して解説してきました．

これらの定理については，より強い主張が知られています．ただし，証明には複素解析学などのより高度な数学が必要になるため，ここでは主張の紹介のみに留めます．

【定理 11】（素数定理）
次が成り立つ． $$ \pi(N)=\frac{N}{\log N}\cdot (1+\mathrm{o}(1)). $$ なお，$\mathrm{o}$ 記法を使わず表すと，次のようにも書ける． $$ \lim_{N\to \infty}\frac{\pi(N)\log N}{N}=1. $$

素数定理は $\pi(N)$ がおおよそ $\dfrac{N}{\log N}$ であるという主張だといえますが，この近似の誤差についてもより詳しいことが知られています．また，Riemann 予想と呼ばれる重要な未解決問題が，$\pi(N)$ の精密な評価を与えることと同値であることが知られています．

【定理 12】（Mertens の定理）
ある定数 $B$（Mertens 定数という）が存在して，次が成り立つ． $$ \sum_{p\le N}\frac{1}{p}=\log\log N + B + \mathrm{o}(1). $$

なお，素数定理を認めたうえで本記事内 【定理 5】 の証明と同じ議論をすれば，$\sum_{p\le N}\dfrac{1}{p}=\log\log N(1+\mathrm{o}(1))$ を示すことは可能です．この定理はそれよりも強い主張をしています．

【定理 13】
$$ \sum_{p\le N}\log p =N (1+\mathrm{o}(1)). $$

なお，素数定理を認めたうえで本記事内 【定理 6】 と同じ議論をすればこの定理を証明することができます．ただし，素数定理の証明では，【定理 13】 を示すことによって素数定理を示すという順も標準的です．

【定理 14】
$$\log\left(\mathrm{lcm}(1,2,\ldots,N)\right)=N(1+\mathrm{o}(1)).$$

この定理から何らかの意味で，$\mathrm{lcm}(1,2,\ldots,N)$ は $e ^ N$ 程度だということもできます．ただし $\mathrm{lcm}(1,2,\ldots,N)=\Theta(e ^ N)$ は成り立たないので注意してください．

【定理 15】
$$ \max (\omega(1),\ldots,\omega(N)) = \frac{\log N}{\log\log N}\cdot (1+\mathrm{o}(1)). $$

$\omega(n)$ のように $n$ の大きさが同じくらいでもその値が大きく増減するような関数については，他に $1\leq n\leq N$ での総和や平均について調べることも標準的です．例えば

$$\sum_{n=1} ^ N \omega(n) = N \log\log N (1+\mathrm{o}(1))$$

などの結果が知られています．

【定理 16】
ある正定数 $C$ が存在して，次が成り立つ． $$ \max_{n\leq N}\frac{n}{\varphi(n)}=(C+\mathrm{o}(1))\log\log N. $$

なお $C$ は Euler 定数 $\gamma$ を用いて $C=e^{\gamma}$ と表されます．ここでは $\gamma$ の定義は省略します．

6. 関連問題

特にありません．

7. まとめ

本記事では素数定理をはじめとする素数に関する評価について，主張を弱めたうえで，高校数学レベルの数学で証明しました．

競技プログラミングにおいては，これらの評価は知識として結果だけ知っておけば十分であったり，オーダーを正確に知らなくとも制約内である程度見積もれるといったものも多いと思います．したがって本記事の内容が直接競技プログラミングに活用できる場面はあまりないと思います．

しかし，素数は自然数そのものの構造に深く関わる，自然科学の重要な基礎のひとつです．競技プログラミングをきっかけに，こういった理論にも触れて，さらに競技プログラミングや自然科学を楽しむ助けになれば嬉しく思います．

8. 参考文献

1. Wikipedia．素数．https://ja.wikipedia.org/wiki/素数．（閲覧日: 2026-03-10）．
2. Wikipedia．素数定理．https://ja.wikipedia.org/wiki/素数定理．（閲覧日: 2026-03-10）．
3. Wikipedia．素数計数関数．https://ja.wikipedia.org/wiki/素数計数関数．（閲覧日: 2026-03-10）．
4. Wikipedia．チェビシェフ関数．https://ja.wikipedia.org/wiki/チェビシェフ関数．（閲覧日: 2026-03-10）．
5. Tom M. Apostol．Introduction to Analytic Number Theory．Springer-Verlag．1976．https://link.springer.com/book/10.1007/978-1-4757-5579-4．
6. Wikipedia．Proof of Bertrand's postulate．https://en.wikipedia.org/wiki/Proof_of_Bertrand%27s_postulate．（閲覧日: 2026-03-10）．
7. maspy．素数に関する上からの評価（初等的な証明）．https://maspypy.com/素数に関する上からの評価（初等的な証明）．（閲覧日: 2026-03-10）．

---

トップページ：AtCoder Algorithm Lectures

---