[PHP]素因数分解を行う。
PHPで約数、素数、最大公約数を求める勉強をしたので最小公倍数を求めてみようと思いました。
とりあえず、ツールだけ使いたいという方は以下のリンクからどうぞ。
https://willdosomeday.com/tools/factoring.phpそこで、単純な疑問。最小公倍数の求め方とは？
2つの数の最小公倍数を求める場合、最大でa×bが答えになることは分かります。
ただ、乗算なので馬鹿正直にそれぞれの数字に１つずつ、a×bの答えまで掛けていって最小の公倍数を拾っていたらとてつもなく処理が膨大になります。
ということで、基本的な最小公倍数の求め方からおさらい。
以下のサイトで勉強しました。
https://juken-mikata.net/how-to/mathematics/east-common-mult...最小公倍数を求めるにはまずは素因数分解から。
ということで、素因数分解を行うプログラムをお勉強。
プログラムに進む前にまずは、、
素因数分解とは
素因数分解とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する。
https://ja.wikipedia.org/wiki/%E7%B4%A0%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3
対象の数の素数の積 を求めればよいということであろう。
対象の数を素数でひたすら割れなくなるまで割っていけばよいということです。
例えば、100の場合
100÷2=50
50÷2=25
25÷5=5
5÷1=5
答えが素数になったところで終了
2*2*5*5=100
本来は「2の自乗×5の自乗」と書かなくてはいけないのですが、PHPで計算を行ううえではそのように記載する必要はないのであえて上記のように記載。
PHPでの計算方法
ということで、以下のような順序で計算を行う。
- 対象の数を小さい素数から割っていく
- 割り切れたらその素数は素因数
- 割り切れた場合、割った答えを再度小さい素数から割っていく
- 答えが素数になるまで繰り返す。
小生には少し難しかったので以下のブログで紹介されていた関数を自分なりに解釈してみました。
http://blog.livedoor.jp/nakamura_tech/archives/51357622.html$n = 10000; //素因数分解を行う数字
$init = 2; //１以外の最初の素数
while ($n !== 1) { //$nが1になるまで繰り返す
$i = $init; while ($i < 0xFFFFFF) { //$iの上限を設定
if ($n % $i == 0) { //$nが$iで割り切れた場合
$result[] = $i; //$iを素因数として配列に格納
$n /= $i; //$nを$iで割って$nに代入。
echo "{$i}で割れました<BR>"; break; //Whileを抜ける
} $i++; //$iに1をプラス
}
$init = $i; }理屈ではわかっていますが、説明できない項目が数点あります。とりあえず動作しているの良しとしましょう。
上記では対象の数が1の場合の処理は入っていません。
諸々の処理を加えたツールを作成しました。以下のリンクからご利用ください・
※サーバーへの過負荷を避けるため、上限を1000000000000に設定しています。