素数かどうかを判定しよう

このレッスンでは、ある数が素数かどうかを判定するアルゴリズムを学び、効率的な判定方法を理解することを目標にします。「PHP 素数判定」で検索している方向けの内容です。

ある数が素数(1とその数自身でしか割り切れない数)かどうかは、2から「その数の平方根」までの数で割り切れるかを調べればわかります。すべて割り切れなければ素数です。

サンプルコードでは、$i * $i <= $nという条件を使うことで、実質的に「平方根まで」の範囲だけをループしています。この書き方だと、あらためて平方根を計算するコストを省略できる、少し工夫されたアルゴリズムになっています。

初心者がよくつまずくのが、なぜ平方根までしか調べなくてよいのかという理屈です。ある数を割り切る2つの数のペアは、必ず一方が平方根以下、もう一方が平方根以上になるため、平方根以下の範囲だけ調べれば十分だという性質を利用しています。

暗号技術の基礎にも使われる重要な数学的性質で、効率よく判定するアルゴリズムを考える良い練習になります。エラトステネスの篩(ふるい)という、複数の素数を一度に効率よく求める発展的な手法も存在します。

📖 お手本コード

<?php
function isPrime($n) {
    if ($n < 2) return false;
    for ($i = 2; $i * $i <= $n; $i++) {
        if ($n % $i === 0) return false;
    }
    return true;
}

var_dump(isPrime(17));
var_dump(isPrime(18));

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではPHPを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
入力された数が素数かどうかを判定するツールが作れるようになります。