はじめに

「素数はどのくらいの頻度で現れるのか？」

この問いに対する答えは、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)