[PHP] 最大公約数を求めるスクリプト(array_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」 とは複数の配列から共通する値を取り出す関数です。
この関数を使用することにより2つの数字の約数から共通する値を公約数として取り出せます。
$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 に設定しています。
ディスカッション
コメント一覧
まだ、コメントがありません