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

            本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下：
[U]复制代码[/U] 代码如下:= 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
希望本文所述对大家的php程序设计有所帮助。
            
            
您可能感兴趣的文章:

php数组函数序列之array_sum() - 计算数组元素值之和

php数字游戏 计算24算法

PHP中计算字符串相似度的函数代码

用php简单实现加减乘除计算器

PHP实现的简单三角形、矩形周长面积计算器分享

PHP计算百度地图两个GPS坐标之间距离的方法

php计算多维数组中所有值总和的方法

PHP计算加权平均数的方法

PHP概率计算函数汇总

php计算多个集合的笛卡尔积实例详解

PHP基于自定义函数生成笛卡尔积的方法示例