這篇文章主要介紹了php計算兩個整數(shù)的最大公約數(shù)常用算法,實例總結(jié)了求最大公約數(shù)的三種常用方法,具有一定參考借鑒價值,需要的朋友可以參考下

本文實例講述了php計算兩個整數(shù)的最大公約數(shù)常用算法。分享給大家供大家參考。具體如下：

代碼如下:

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

}

//////////////////////////////////////////

//基于最大公約數(shù)的定義

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;

}

////////////////////////////////////////////

//中學數(shù)學里面的計算方法

function baseSchool($m, $n) {

$mp = getList($m); //小于$m的全部質(zhì)數(shù)

$np = getList($n); //小于$n的全部質(zhì)數(shù)

$mz = array(); //保存$m的質(zhì)因數(shù)

$nz = array(); //保存$n的質(zhì)因數(shù)

$mt = $m;

$nt = $n;

//m所有質(zhì)因數(shù)

//遍歷m的全部質(zhì)數(shù)，當能夠被m整除時，繼續(xù)下一次整除，知道不能被整除再取下一個能夠被m整除

//的質(zhì)數(shù)，一直到所有出現(xiàn)的質(zhì)數(shù)的乘積等于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所有質(zhì)因數(shù)

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;

}

}

}

//公因數(shù)

$jj = array_intersect($mz, $nz); //取交集

$gys = array();

//取出在倆數(shù)中出現(xiàn)次數(shù)最少的因數(shù)，去除多余的。

$c = 1; //記錄數(shù)字出現(xiàn)的次數(shù)

$p = 0; //記錄上一次出現(xiàn)的數(shù)字

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的整數(shù)的連續(xù)質(zhì)數(shù)序列

//埃拉托色尼篩選法

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

希望本文所述對大家的php程序設計有所幫助。

更多信息請查看IT技術(shù)專欄