php计算两个整数的最大公约数常用算法小结

本文实例讲述了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 $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 secondsecho baseSchool(60, 24);   //0.0003471375 seconds$time_end  =  microtime_float ();$time  =  $time_end  -  $time_start ;echo "<br>" . sprintf("%1.10f", $time) . "seconds";

希望本文所述对大家的php程序设计有所帮助。