[PHP] 最大公約数を求めるスクリプト(array_intersect)

PHParray_intersect, 最大公約数, 約数

素数・約数を調べるスクリプトを書いたので、これらを使って最大公約数を求めるスクリプトを作成しました。

最大公約数とは

最大公約数とは、少なくとも一つが0ではない複数の整数の公約数のうち最大の数を指す。

https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0

英語では「Greatest common divisor」といいます。

今回は二つの数字の最大公約数を求めます。

約数を求める

約数を求める関数は以前に作ったものをそのまま使います。

function divisor($num) {
$limit = sqrt($num);
for($i=1;$i<=$limit;$i++) {
if($num%$i == 0) {
$j[] = $i;
$k = $num/$i;
if ($i!=$k) {
$j[] = $k;
}
}
}
sort($j);
return $j;
}

約数から公約数を抽出する(array_intersect)

2つの数字の約数を調べたら「array_intersect」を使用して公約数を調べます。

「array_intersect」 とは複数の配列から共通する値を取り出す関数です。

この関数を使用することにより２つの数字の約数から共通する値を公約数として取り出せます。

$a = 15;
$b = 180:

$c = divisor($a);
$d = divisor($b);

$e = array_intersect($c, $d);

以下が出力結果です。

15の約数

1 3 5 15

180の約数

1 2 3 4 5 6 9 10 12 15 18 20 30 36 45 60 90 180

公約数

1 3 5 15

最大公約数を調べる(end)

当たり前のことではありますが、取り出した公約数の中で一番大きい数字が最大公約数になります。

約数を調べるときに配列をsort関数を使用して昇順に並べ替えているので、array_intersect関数で公約数を取り出した結果も昇順に並んでいる(はず)。

ということで、end関数で配列の最後の値を取得します。

end関数とは配列の一番最後の値を取得する関数です。

$f = end($e);

まとめ

//約数を調べる関数
function divisor($num) {
$limit = sqrt($num);
for($i=1;$i<=$limit;$i++) {
if($num%$i == 0) {
$j[] = $i;
$k = $num/$i;
if ($i!=$k) {
$j[] = $k;
}
}
}
sort($j);
return $j;
}

//調べる2つの値
$a = 15;
$b = 180:

//a,bそれぞれの約数を配列に格納
$c = divisor($a);
$d = divisor($b);

//公約数をチェック
$e = array_intersect($c, $d);

//最大公約数をチェック
$f = end($e);

デモ

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

約数同様にチェックできる上限を10000000000000 に設定しています。

PHParray_intersect, 最大公約数, 約数