[PHP]自然数の約数を調べるスクリプト

PHP平方根, 約数

特定の数字を指定してその数字を割り切れるを調べる。

英語で約数は「Divisor」といいます。

解説なんかはどうでもいいので約数を調べるツールを使用したいという方は以下からどうぞ。

約数とは

数学において、整数 N の約数（やくすう、英: divisor）とは、N を割り切る整数またはそれらの集合のことである。

https://ja.wikipedia.org/wiki/%E7%B4%84%E6%95%B0

約数チェック

どのようにして約数をチェックするか考えてみる。

わかりやすい例として１００で検証

1100
250
425
520
1010平方根
205
254
502
1001

100の約数は上記のようになる。

表の平方根より下の列はすでに出ている約数と重複している。よって平方根までチェックすれば全ての約数を確認できるはず。

ということで、チェックするスクリプトは以前調べた素数の求め方を基本として作成してみる。

(素数の求め方も平方根まで約数があるかをチェックするため)

以下の関数を流用

function primeNumber($target) {
$limit = sqrt($target);
$res = NULL; 
for($i=2;$i>=$limit ;$i++) {
if($target%$i == 0) { 
$res = $i;
break;
}
}
}

関数名がprimeNumberのままなのはアレなのでdivisorに変更。

今回は余りがゼロの場合が約数になるので「$target%$i == 0」の場合、配列に$iを代入。

function divisor($target) {

$limit = ceil(sqrt($target));

for($i=1;$i<=$limit;$i++) {
if($target%$i == 0) {
$divisor_array[] = $i;
}
}
}

しかし、これだと平方根以上の約数が求められないので、以下を追記

function divisor($target) {

$limit = ceil(sqrt($target));

for($i=1;$i<=$limit;$i++) {
if($target%$i == 0) {
$divisor_array[] = $i;
$j = $num/$i; //$iで割り切れる数を求める。
if ($i!=$j) { //平方根ではない場合
$divisor_array[] = $j; //約数の配列に代入
}
}
}
return $divisor_array;
}

これで完成。ただし、平方根までいちいち計算するので、もっと効率の良い方法があるはず。思いついたら追記します。

デモ

値を入力して約数をチェックできるサンプルを作成しました。

※サーバーに負荷がかかるのでチェック可能な数字の上限を 10000000000000 に設定しています。

PHP平方根, 約数