<?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';