php計算兩個整數的最大公約數常用算法小結

2020-03-22 18:28:07

字體：大中小

來源：轉載

供稿：網友

本文實例講述了php計算兩個整數的最大公約數常用算法。分享給大家供大家參考。具體如下：復制代碼代碼如下: php
//計時，返回秒
function microtime_float ()
{
list( $usec , $sec ) = explode ( " " , microtime ());
return ((float) $usec + (float) $sec );
}
//////////////////////////////////////////
//歐幾里得算法
function ojld($m, $n) {
if($m ==0 && $n == 0) {
return false;
}
if($n == 0) {
return $m;
}
while($n != 0){
$r = $m % $n;
$m = $n;
$n = $r;
}
return $m;
}
//////////////////////////////////////////
//基于最大公約數的定義
function baseDefine($m, $n) {
if($m ==0 && $n == 0) {
return false;
}
$min = min($m, $n);
while($min = 1) {
if($m % $min == 0){
if($n % $min ==0) {
return $min;
}
}
$min -= 1;
}
return $min;
}
////////////////////////////////////////////
//中學數學里面的計算方法
function 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){
break 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){
break 2;
}
}
}
//公因數
$jj = array_intersect($mz, $nz); //取交集
$gys = array();
//取出在倆數中出現次數最少的因數，去除多余的。
$c = 1; //記錄數字出現的次數
$p = 0; //記錄上一次出現的數字
sort($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 $html' target='_blank'>value) {
$count *= $value;
}
return $count;
}
//求給定大于等于2的整數的連續質數序列
//埃拉托色尼篩選法
function getList($num) {
$a = array();
$a = array();
for($i = 2; $i = $num; $i++) {
$a[$i] = $i;
}
for( $i = 2; $i = floor( sqrt($num) ); $i++ ) {
if($a[$i] != 0) {
$j = $i * $i;
while($j = $num) {
$a[$j] = 0;
$j = $j + $i;
}
}
}
$p = 0;
for($i = 2; $i = $num; $i++) {
if($a[$i] != 0) {
$L[$p] = $a[$i];
$p++;
}
}
return $L;
}
/////////////////////////////////////
//test
$time_start = microtime_float ();
//echo ojld(60, 24); //0.0000450611 seconds
//echo baseDefine(60, 24); //0.0000557899 seconds
echo baseSchool(60, 24); //0.0003471375 seconds
$time_end = microtime_float ();
$time = $time_end - $time_start ;
echo ' br ' . sprintf('%1.10f', $time) . 'seconds';希望本文所述對大家的php程序設計有所幫助。PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。

上一篇：PHP實現堆排序算法（代碼示例）

下一篇：PHP實現的簡單組詞算法示例講解