php如何计算两个整数的最大公约数
创始人
2024-12-12 10:01:19
0次

具体如下:

= 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 seconds
echo baseSchool(60, 24);   //0.0003471375 seconds
$time_end  =  microtime_float ();
$time  =  $time_end  -  $time_start ;
echo '
' . sprintf('%1.10f', $time) . 'seconds';

相关内容

热门资讯

空调连续工作多久需要停机休息 空调连续工作的时间取决于多个因素,包括空调的型号、功率、使用环境和维护情况等。一般来说,空调可以连续...
空调哪个符号是除湿的 空调除湿功能通常用一个水滴形状的符号表示。不同品牌和型号的空调遥控器可能会有所差异,但一般来说,除湿...
格力空调多长时间加一次氟利昂 1、一般情况下,空调对氟利昂的使用量是非常小的,所以在空调使用了四年左右的时候再考虑加也没问题。2、...
空调用多长时间需要加氟一次 一般情况下是五年。当出现以下这几种情况时,空调才需要加氟。1、空调的室内机和室外机各有两个接口,当接...
格调生活·C标思享荟:卡萨帝在... 9月12日的郑州龙湖金融岛,夜风轻拂,灯光璀璨。“C标时刻共传奇——卡萨帝思享荟暨20周年品牌盛典郑...
品牌价值破千亿、高端份额持续领... 9月12日,“C标时刻共传奇——卡萨帝思享荟暨20周年品牌盛典郑州站”在郑州龙湖金融岛举办。2026...
空调主板坏了修800还是换新的 空调主板坏了是修还是换新,需要考虑多个因素,以下是一些建议:1. 维修成本:如果维修费用较低,比如 ...
空调开多久需要休息多长时间 问题:空调开多久需要休息多长时间回答:1、在使用空调的过程中,一般空调开7~8个小时左右需要休息2~...
中央空调多长时间清洗一次 1、一般空调开机前清洗一次即可,空调开机中间时段再清洗一次,空调关机时清洗一次,这样比较合理。2、空...
中央空调氟利昂多久加一次 看空调制热和制冷程度,很多人的观点认为氟利昂必须一年放一次,其实这个观点是错误的,理解上面有点偏差,...