素数と素因数分解——整数の原子

素数とは

「物質を分解していくと最終的に原子に行き着く」——整数の世界でも同じことが言えます。どんな整数も素数の積に分解でき、その素数はこれ以上分解できません。素数は「整数の原子」です。

$2$ 以上の整数で、$1$ と自分自身以外に正の約数を持たない数を素数（prime number）といいます。

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots$

素数でない $2$ 以上の整数は合成数（composite number）といいます——「複数の素数の積として表せる数」。

$1$ は素数でも合成数でもない「特別な数」です（算術の基本定理が成立するよう定義から除外されています）。

エラトステネスの篩

「100 以下の素数を全部見つけたい」——一つ一つ確認していくのは大変なので、「消去法」で一気に見つけます。これが紀元前のギリシャの数学者エラトステネスが考えた篩（ふるい）の方法です。

$100$ 以下の素数をすべて求めるアルゴリズムです。

手順：

1. $2$ から $100$ まで並べる
2. $2$ を残し、$2$ の倍数をすべて消す——「2 の倍数は合成数なので消す」
3. 次の残った数（$3$）を残し、$3$ の倍数をすべて消す
4. $\sqrt{100} = 10$ まで繰り返す
5. 残った数がすべて素数——「消されなかったものだけが素数」

$\sqrt{n}$ まで調べればよい理由：合成数 $n = ab$（$a \le b$）では $a \le \sqrt{n}$ が必ず成立するため——「小さい方の因数は必ず $\sqrt{n}$ 以下にいる」。

アニメーション：エラトステネスの篩

var sieve, phase, timer, currentPrime, N;
N = 100;

sieve = [];
for (var ii = 0; ii <= N; ii++) sieve.push(true);
sieve[0] = false; sieve[1] = false;

phase = 0;
timer = 0;
currentPrime = 2;
var eliminated = [];
for (var ei = 0; ei <= N; ei++) eliminated.push(false);

function loop() {
ctx.clearRect(0, 0, W, H);
timer++;

// advance sieve step
if (timer % 6 === 0 && currentPrime <= 10) {
  // mark next multiple
  var next = -1;
  for (var m = currentPrime * 2; m <= N; m += currentPrime) {
    if (!eliminated[m]) { next = m; break; }
  }
  if (next !== -1) {
    eliminated[next] = true;
    sieve[next] = false;
  } else {
    // find next prime
    var found = false;
    for (var np = currentPrime + 1; np <= 10; np++) {
      if (sieve[np]) { currentPrime = np; found = true; break; }
    }
    if (!found) currentPrime = 11;
  }
}

var cols = 10;
var cellW = (W - 40) / cols;
var cellH = 28;
var ox = 20, oy = 30;

for (var num = 1; num <= N; num++) {
  var row = Math.floor((num - 1) / cols);
  var col = (num - 1) % cols;
  var cx = ox + col * cellW;
  var cy = oy + row * cellH;

  var isPrime = sieve[num];
  var isElim = eliminated[num] || (!isPrime && num > 1);
  var isCurrent = (num !== currentPrime && num > 1 && num % currentPrime === 0 && currentPrime <= 10 && num <= N);

  if (num === currentPrime && currentPrime <= 10) {
    ctx.fillStyle = '#fbbf24';
  } else if (isPrime) {
    ctx.fillStyle = '#22c55e';
  } else if (isElim && num > 1) {
    ctx.fillStyle = '#1e293b';
  } else {
    ctx.fillStyle = '#1e293b';
  }

  ctx.fillRect(cx + 1, cy + 1, cellW - 2, cellH - 2);

  if (num === 1) {
    ctx.fillStyle = '#475569';
  } else if (num === currentPrime && currentPrime <= 10) {
    ctx.fillStyle = '#0d1117';
  } else if (isPrime) {
    ctx.fillStyle = '#0d1117';
  } else {
    ctx.fillStyle = '#334155';
  }
  ctx.font = 'bold 12px monospace';
  ctx.textAlign = 'center';
  ctx.fillText(num, cx + cellW/2, cy + cellH/2 + 4);
}

ctx.fillStyle = '#e2e8f0';
ctx.font = '13px monospace';
ctx.textAlign = 'left';
ctx.fillText('現在の篩: ' + (currentPrime <= 10 ? currentPrime + ' の倍数を消去中' : '完了'), 20, 320);

ctx.fillStyle = '#22c55e';
ctx.fillText('■ 素数', W - 160, 320);
ctx.fillStyle = '#fbbf24';
ctx.fillText('■ 現在の素数', W - 80, 340);

requestAnimationFrame(loop);
}
loop();

算術の基本定理

「どんな整数も素数の積に一意に分解できる」——これが数論の根幹をなす定理です。一意というのは「分解の方法は（順序を無視すれば）1通りしかない」という意味です。

定理：$2$ 以上の整数はすべて素数の積として一意に表せる。

$n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k} \quad (p_1 < p_2 < \cdots < p_k \text{ は素数})$

この「一意性」が整数の算術を美しくする本質です——「どんな順番で因数分解しても、必ず同じ答えになる」。

例： $360 = 2^3 \times 3^2 \times 5 = 8 \times 9 \times 5$

素因数分解の手順

「$360$ を素数の積に分解する」——小さい素数から順に割り続けるだけです：

$n = 360$ を素因数分解：

360 ÷ 2 = 180
180 ÷ 2 = 90
 90 ÷ 2 = 45
 45 ÷ 3 = 15
 15 ÷ 3 = 5
  5 ÷ 5 = 1
→ 360 = 2³ × 3² × 5

計算量：$O(\sqrt{n})$——「$\sqrt{360} \approx 19$ まで試せば十分」。

素数の分布と素数定理

「素数はどのくらい密に分布しているか」——$n$ 以下の素数の個数を $\pi(n)$ と表します。

素数定理（1896年証明）：

$\pi(n) \sim \frac{n}{\ln n} \quad (n \to \infty)$

素数は無限に存在します（ユークリッドの証明、紀元前）。

証明（背理法）：「素数が有限個しかない」と仮定すると矛盾が生じる——素数が $p_1, \ldots, p_k$ しかないと仮定すると、$N = p_1 p_2 \cdots p_k + 1$ はどの素数でも割り切れないが、1より大きいので素因数を持つ——矛盾。

メルセンヌ素数

「$2^p - 1$ の形の素数」——コンピュータを使って今も新しい素数を探し続けているのがメルセンヌ素数です：

$M_p = 2^p - 1$（$p$ は素数）が素数のとき、メルセンヌ素数と呼びます。

2025年現在、最大の既知素数はメルセンヌ素数 $2^{136279841}-1$（約4100万桁！）——「人類がコンピュータを使って見つけた最大の素数」。

RSA 暗号と素数

「インターネットで買い物をするとき、クレジットカード番号を安全に送るしくみ」——現代のインターネット通信を守るRSA 暗号は素因数分解の困難さに基づいています：

• 2つの大きな素数 $p, q$ を選び $n = pq$ を公開
• $n$ から $p$ と $q$ を求めること（素因数分解）は計算上非常に困難——「掛けるのは簡単だが、逆算は難しい」
• 典型的な鍵サイズ：2048ビット（約600桁の数）

まとめ

• 素数：1と自分自身しか約数を持たない数（2, 3, 5, 7, 11, …）——「整数の原子」
• エラトステネスの篩：$\sqrt{n}$ まで調べて $n$ 以下の素数を列挙——「消去法で一気に発見」
• 算術の基本定理：任意の整数は素数の積として一意に分解できる——「分解方法は1通りしかない」
• 素数は無限に存在する（ユークリッドの背理法）——「どれだけ大きくても次の素数がある」
• 素数定理：$n$ 以下の素数は約 $n/\ln n$ 個
• 素数は現代暗号の基盤——「インターネットセキュリティを支える」

次回は合同式（モジュラー算術）——時計の算数と整数の剰余を学びます。