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 seconds

　　echo baseSchool(60, 24);   //0.0003471375 seconds

　　$time_end  =  microtime_float ();

　　$time  =  $time_end  -  $time_start ;

　　echo '<br>' . sprintf('%1.10f', $time) . 'seconds';