はじめに
「素数はどのくらいの頻度で現れるのか？」
この問いに対する答えは、19世紀に数学者たちが長年追い求めた素数定理として結実している。本記事では、Python を使って $n$ 以下の素数の個数 $\pi(n)$ を数え、その比 $\pi(n)/n$ をグラフに描くことで、素数定理が予言する振る舞いを視覚的に確かめる。ただし、今回の記事はClaudeCodeを用いた。
素数とは
素数とは、1 より大きい整数のうち、1 と自分自身以外に正の約数を持たない数のことである。
$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ \ldots$$
素数は無限に存在する（ユークリッドによる古典的な証明が有名である）。しかし、その分布は一様ではなく、大きな数になるほど素数は「まばら」になっていく。
素数定理
$n$ 以下の素数の個数を $\pi(n)$（素数計数関数）と表す。素数定理は次を主張する。
$$\boxed{\pi(n) \sim \frac{n}{\ln n} \quad (n \to \infty)}$$
ここで $f(n) \sim g(n)$ は $n \to \infty$ のとき $f(n)/g(n) \to 1$ を意味する。
言い換えると、
$$\frac{\pi(n)}{n} \sim \frac{1}{\ln n} \quad (n \to \infty)$$
が成り立つ。つまり「$n$ 付近のランダムな整数が素数である確率はおよそ $\frac{1}{\ln n}$」と解釈できる。
素数定理は 1896 年にアダマールとド・ラ・ヴァレー・プサンが独立に証明した。証明にはリーマンのゼータ関数の解析的性質が用いられ、純粋に初等的な手段では 1949 年にエルデシュとセルバーグが独立に証明するまで待つことになる。
実装
アルゴリズムの選択：エラトステネスの篩
単純な試し割り法では 1 つの数 $m$ の素数判定に $O(\sqrt{m})$ の時間が必要で、$n (= 10^6)$ まで全て調べると合計 $O(n\sqrt{n})$ かかる。
代わりにエラトステネスの篩を使うと $O(n \log \log n)$ で $n$ 以下の全素数を一括で求められる。NumPy の配列演算と組み合わせることで、$n = 10^6$ でも非常に高速に動作する。
コード
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
N = 10**6
def sieve_of_eratosthenes(limit):
"""エラトステネスの篩で limit 以下の素数を求める"""
is_prime = np.ones(limit + 1, dtype=bool)
is_prime[0:2] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
is_prime[i*i::i] = False
return is_prime
is_prime = sieve_of_eratosthenes(N)
x = np.arange(1, N + 1)
prime_count = np.cumsum(is_prime[1:N + 1]) # π(n)
ratio = prime_count / x # π(n)/n
# 素数定理の理論値: π(n)/n ≈ 1/ln(n)
theoretical = 1.0 / np.log(x[1:]) # n=1 は log(1)=0 で除算不能のため除外
x_theory = x[1:]
plt.figure(figsize=(10, 6))
plt.plot(x, ratio, color='blue', linewidth=0.8, label=r'$\pi(n)/n$（実測値）')
plt.plot(x_theory, theoretical, color='red', linewidth=1.2, linestyle='--',
label=r'$1/\ln(n)$（素数定理による近似）')
plt.xlabel('n')
plt.ylabel(r'$\pi(n)/n$')
plt.title(r'素数の個数のグラフ：$\pi(n)/n$ と素数定理')
plt.legend()
plt.tight_layout()
plt.savefig(f"prime_number_theorem_{N}.png", dpi=150)
plt.show()
コードのポイント
| 箇所 | 説明 |
|---|---|
np.ones(..., dtype=bool) |
全要素を「素数候補」として初期化する |
is_prime[i*i::i] = False |
$i$ の倍数を一括で篩い落とす（$i^2$ 未満はすでに処理済みである） |
np.cumsum(...) |
インデックス $n$ までの素数の個数 $\pi(n)$ を累積和で $O(n)$ で計算する |
1.0 / np.log(x[1:]) |
素数定理の理論曲線 $1/\ln(n)$（$n=1$ は除外） |
結果と考察
実行すると、以下のようなグラフが得られる。
- 青線（実測値）：$\pi(n)/n$ の実際の値
- 赤破線（理論値）：$1/\ln n$
グラフから、$n$ が大きくなるにつれて両者が接近していく様子が確認できる。これは素数定理の主張そのものである。
なお、$n = 10^6$ 時点でも完全には一致していない。これは「$\sim$」が漸近的な等式（極限での比が 1 に収束）を意味しており、有限の $n$ では誤差が残るためである。理論値との差（相対誤差）は $n$ が大きいほど小さくなる。
より精密な近似としては、対数積分
$$\mathrm{Li}(n) = \int_2^n \frac{dt}{\ln t}$$
を用いると $\pi(n)$ との一致が格段に向上することが知られている。
まとめ
- 素数定理 $\pi(n)/n \sim 1/\ln n$ を Python で可視化した
- エラトステネスの篩と NumPy の累積和を組み合わせることで、$n = 10^6$ を高速に処理できた
- グラフから、実測値が理論値に収束していく様子を視覚的に確認できた
素数の分布はシンプルな法則に従いながらも、その証明は深い解析学を要する。可視化によって直感的な理解の一助となれば幸いである。
参考文献
-
G.H. Hardy, E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press
-
松坂和夫, 『解析入門』, 岩波書店
-
Wikipedia: 素数定理
-
エラトステネスの篩
(https://manabitimes.jp/math/992)