PHP_PHP チュートリアルで 2 つの整数の最大公約数を計算するための一般的なアルゴリズムの概要

PHPで2つの整数の最大公約数を計算するためによく使われるアルゴリズムのまとめ

この記事では、PHPで2つの整数の最大公約数を計算するためによく使われるアルゴリズムを主に紹介します。例では、最大公約数には特定の基準値があり、困っている友達はそれを参照できます

この記事の例では、PHP で 2 つの整数の最大公約数を計算する一般的なアルゴリズムについて説明します。参考のためにみんなで共有してください。詳細は以下の通りです

コードは次のとおりです:

//タイマー、秒を返します
関数 microtime_float ()
{
list( $usec , $sec ) =explode ( " " , microtime ());
return ((float) $usec + (float) $sec );
}
//////////////////////////////////////////
//ユークリッドアルゴリズム
関数 ojld($m, $n) {
if($m ==0 && $n == 0) {
false を返します;
}
if($n == 0) {
$m を返します;
}
while($n != 0){
$r = $m % $n;
$m = $n;
$n = $r;
}
$m を返します;
}
//////////////////////////////////////////
//最大公約数の定義に基づく
関数baseDefine($m, $n) {
if($m ==0 && $n == 0) {
false を返します;
}
$min = min($m, $n);
while($min >= 1) {
if($m % $min == 0){
if($n % $min ==0) {
$min を返します;
}
}
$min -= 1;
}
$min を返します;
}
/////////////////////////////////////////////
//中学数学の計算方法
関数baseSchool($m, $n) {
$mp = getList($m) //$m より小さいすべての素数
$np = getList($n); //$n より小さいすべての素数
$mz = array(); // $m
の素因数を保存します $nz = array(); // $n の素因数を保存
$mt = $m;
$nt = $n;
// m
のすべての素因数 // m のすべての素数を調べます。それらが m で割り切れないことがわかっている場合は、次の m で割り切れる整数の割り算を実行します。 //素数、出現するすべての素数の積が m
に等しい場合に停止します foreach($mp as $v) {
while($mt % $v == 0) {
$mz[] = $v;
$mt = $mt / $v;
}
$c = 1;
foreach($mz as $v) {
$c *= $v;
if($c == $m){
休憩 2;
}
}
}
//nすべての素因数
foreach($np as $v) {
while($nt % $v == 0) {
$nz[] = $v;
$nt = $nt / $v;
}
$c = 1;
foreach($nz as $v) {
$c *= $v;
if($c == $n){
休憩 2;
}
}
}
//共通因数
$jj = array_intersect($mz, $nz) //交差点を取得します
; $gys = array();
//2 つの数値のうち、最も出現頻度の低い因数を取り出し、冗長なものを削除します。
$c = 1; // 数字が出現した回数を記録します
$p = 0 //最後に出現した数値を記録します
; 並べ替え($jj);
foreach($jj as $key => $v) {
if($v == $p) {
$c++;
}
elseif($p != 0) {
$c = 1;
}
$p = $v;
$mk = array_keys($mz, $v);
$nk = array_keys($nz, $v);
$k = ( count($mk) > count($nk) ) ? count($nk) : count($mk);
if($c > $k) {
unset($jj[$key]);
}
}
$count = 1;
foreach($jj as $value) {
$count *= $value;
}
$count を返します;
}
// 2 以上の指定された整数の連続する素数のシーケンスを見つけます
//エラトステネスのスクリーニング法
関数 getList($num) {
$a = 配列();
$a = 配列();
for($i = 2; $i $a[$i] = $i;
}
for( $i = 2; $i if($a[$i] != 0) {
$j = $i * $i;
while($j $a[$j] = 0;
$j = $j + $i;
}
}
}
$p = 0;
for($i = 2; $i if($a[$i] != 0) {
$L[$p] = $a[$i];
$p++;
}
}
$L を返します;
}
//////////////////////////////////////
//テスト
$time_start = microtime_float ();
//エコー ojld(60, 24) //0.0000450611 秒
//エコーbaseDefine(60, 24) //0.0000557899秒
; echo BaseSchool(60, 24) //0.0003471375 秒
$time_end = microtime_float ();
$time = $time_end - $time_start ;
echo '
' . sprintf('%1.10f', $time) .

この記事で説明した内容が皆様の PHP プログラミング設計に役立つことを願っています。

http://www.bkjia.com/PHPjc/963981.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/963981.html技術記事 PHP で 2 つの整数の最大公約数を計算するためによく使用されるアルゴリズムのまとめ この記事では、PHP で 2 つの整数の最大公約数を計算するためによく使用されるアルゴリズムを主に紹介します。 ..