Summary of common algorithms for calculating the greatest common divisor of two integers in PHP_PHP Tutorial

A summary of commonly used algorithms for calculating the greatest common divisor of two integers in PHP

This article mainly introduces the commonly used algorithms for calculating the greatest common divisor of two integers in PHP. The example summarizes how to find the maximum The three commonly used methods of common denominators have certain reference value. Friends in need can refer to them

The example in this article describes the common algorithm for calculating the greatest common divisor of two integers in PHP. Share it with everyone for your reference. The details are as follows:

The code is as follows:

//Timer, return seconds
function microtime_float ()
{
list( $usec , $sec ) = explode ( " " , microtime ());
return ((float) $usec + (float) $sec );
}
///////////////////////////////////////////
//Euclidean algorithm
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;
}
///////////////////////////////////////////
//Definition based on the greatest common divisor
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;
}
//////////////////////////////////////////////
//Calculation methods in middle school mathematics
function baseSchool($m, $n) {
$mp = getList($m); //All prime numbers less than $m
$np = getList($n); //All prime numbers less than $n
$mz = array(); //Save the prime factors of $m
$nz = array(); //Save the prime factors of $n
$mt = $m;
$nt = $n;
//mAll prime factors
//Traverse all the prime numbers of m. When it is divisible by m, continue to the next integer division. If it is not divisible, then take the next one that can be divisible by m
//Prime numbers, stop when the product of all prime numbers that appear is equal to 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;
}
}
}
//nAll prime factors
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;
}
}
}
//Common factors
$jj = array_intersect($mz, $nz); //Get the intersection
$gys = array();
//Take out the factor that appears the least frequently among the two numbers and remove the redundant ones.
$c = 1; //Record the number of times the number appears
$p = 0; //Record the last number that appeared
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;
}
//Find the sequence of continuous prime numbers for a given integer greater than or equal to 2
//Eratosthenes screening method
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';

I hope this article will be helpful to everyone’s PHP programming design.

http://www.bkjia.com/PHPjc/963981.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/963981.htmlTechArticleSummary of common algorithms for calculating the greatest common divisor of two integers in PHP. This article mainly introduces PHP to calculate the greatest common divisor of two integers. Commonly used algorithms for the greatest common divisor. Examples summarize three common methods for finding the greatest common divisor...