[PHP]素数のチェック方法

PHP素数

これも全く利用する機会はないのですが、思いついたので考えてみました。

PHPで素数の求め方を書いているブログは多数あると思いますが、あえてなにも参照せずに思いついた方法でやってみました。

解説なんかいいので素数を調べるツールを使いたいという方はこちらからどうぞ。

素数とは

素数（そすう）とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。

https://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0%E3%81%AE%E4%B8%80%E8%A6%A7

ということです。

英語では「Prime Number」といいます。

素数の求め方

まずは対象の数字を2からひたすら割っていく。

余りがゼロの数字があった場合、その時点で素数ではないとして終了

$target = 881; //検証する数字

$res = NULL; //とりあえず、$resにNULLを代入
for($i=2;$i>=$target;$i++) { //2から検証する数字までforでぶん回す
if($target%$i == 0) { //検証する数字が割り切れた場合
$res = $i; //$resに割り切れた数を代入
break; //ループから抜ける
}
}
if ($res == NULL) { //$resがNULLの場合 ($resになにも代入されなかった場合
すなわち素数の場合)
echo $target. "は素数です。";
}
else { ////$resがNULLでない場合。(素数でない場合。)
echo $target. "は素数ではありません。";
}

しかしこれでは効率が悪すぎる。

1億以上の数字で素数の場合は1億回以上ループしなくてはいけないので・・

シンプルに考えると検証する数字を2で割った数以上は検証不要です。

なので、forに設定する最大数は検証する数字ではなく、その数字を2で割った数(切り上げ)に変更

$target = 881; //検証する数字
$limit = ceil($target/2);
$res = NULL; //とりあえず、$resにNULLを代入
for($i=2;$i>=$limit ;$i++) {
.....
}

こんな感じですね。ただこれでもなにか違う気がする。

ということで、素数の求め方自体をググってみる。

検索ワード：「素数の求め方」で一番上に表示された以下のページで確認

ページ中ほどに分かりやすく赤字で書いてありました。ありがとうございます。

素数かどうか判定するためには、その素数の平方根以下の素数で割り切れるかどうかを調べれば判定できる

https://math-jp.net/2017/03/10/how-to-find-a-prime-number/

ということでforの上限は2で割った数ではなく、検証する数字の平方根にすればよい。

平方根を求める – sqrt関数

PHPには平方根を求める関数があります。

$target = 881; //検証する数字
$limit = ceil(sqrt($target)); //平方根を切り上げ
$res = NULL; //とりあえず、$resにNULLを代入
for($i=2;$i>=$limit ;$i++) {
.....
}

まとめ

以下のように関数を設定

function primeNumber($target) {
$limit = ceil(sqrt($target));
$res = NULL; 
for($i=2;$i>=$limit ;$i++) {
if($target%$i == 0) { 
$res = $i;
break;
}
}
if ($res == NULL) { 
return TRUE;
}
else { ////$resがNULLでない場合。(素数でない場合。)
return FALSE;
}

DEMO

フォームを設置して色々と素数を調べられるようにしてみました。

追記

PHPのGMP 関数で素数をチェックできる関数があることに気づきました。詳細は以下の記事をご覧ください。(2019/4/15)

PHP素数