当前位置:首页 > PHP教程 > php应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-05-15 17:19:40 浏览: 评论:0 

这篇文章主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常用方法,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了php计算两个整数的最大公约数常用算法。分享给大家供大家参考。具体如下:

  1. <?php 
  2. //计时,返回秒 
  3. function  microtime_float () 
  4.     list( $usec ,  $sec ) =  explode ( " " ,  microtime ()); 
  5.     return ((float) $usec  + (float) $sec ); 
  6. ////////////////////////////////////////// 
  7. //欧几里得算法 
  8. function ojld($m$n) { 
  9.     if($m ==0 && $n == 0) { 
  10.         return false; 
  11.     } 
  12.     if($n == 0) { 
  13.         return $m
  14.     } 
  15.     while($n != 0){ 
  16.         $r = $m % $n
  17.         $m = $n
  18.         $n = $r
  19.     } 
  20.     return $m
  21. ////////////////////////////////////////// 
  22. //基于最大公约数的定义 
  23. function baseDefine($m$n) { 
  24.     if($m ==0 && $n == 0) { 
  25.         return false; 
  26.     } 
  27.     $min = min($m$n); 
  28.     while($min >= 1) { 
  29.         if($m % $min == 0){ 
  30.             if($n % $min ==0) { 
  31.                 return $min
  32.             } 
  33.         } 
  34.         $min -= 1; 
  35.     } 
  36.     return $min
  37. //////////////////////////////////////////// 
  38. //中学数学里面的计算方法 
  39. function baseSchool($m$n) { 
  40.     $mp = getList($m); //小于$m的全部质数 
  41.     $np = getList($n); //小于$n的全部质数 
  42.     $mz = array();  //保存$m的质因数 
  43.     $nz = array();  //保存$n的质因数 
  44.     $mt = $m
  45.     $nt = $n
  46.     //m所有质因数 
  47.     //遍历m的全部质数,当能够被m整除时,继续下一次整除,知道不能被整除再取下一个能够被m整除 
  48.     //的质数,一直到所有出现的质数的乘积等于m时停止 
  49.     foreach($mp as $v) { 
  50.         while($mt % $v == 0) { 
  51.             $mz[] = $v
  52.             $mt = $mt / $v
  53.         } 
  54.         $c = 1; 
  55.         foreach($mz as $v) { 
  56.             $c *= $v
  57.             if($c == $m){ 
  58.                 break 2; 
  59.             } 
  60.         } 
  61.     } 
  62.     //n所有质因数 
  63.     foreach($np as $v) { 
  64.         while($nt % $v == 0) { 
  65.             $nz[] = $v
  66.             $nt = $nt / $v
  67.         } 
  68.         $c = 1; 
  69.         foreach($nz as $v) { 
  70.             $c *= $v
  71.             if($c == $n){ 
  72.                 break 2; 
  73.             } 
  74.         } 
  75.     } 
  76.     //公因数 
  77.     $jj = array_intersect($mz$nz); //取交集 
  78.     $gys = array(); 
  79.     //取出在俩数中出现次数最少的因数,去除多余的。 
  80.     $c = 1; //记录数字出现的次数 
  81.     $p = 0; //记录上一次出现的数字 
  82.     sort($jj); 
  83.     foreach($jj as $key => $v) { 
  84.         if($v == $p) { 
  85.             $c++; 
  86.         } 
  87.         elseif($p != 0) { 
  88.             $c = 1; 
  89.         } 
  90.         $p = $v
  91.         $mk = array_keys($mz$v); 
  92.         $nk = array_keys($nz$v); 
  93.         $k = ( count($mk) > count($nk) ) ? count($nk) : count($mk); 
  94.         if($c > $k) { 
  95.             unset($jj[$key]); 
  96.         } 
  97.     } 
  98.     $count = 1; 
  99.     foreach($jj as $value) { 
  100.         $count *= $value
  101.     } 
  102.     return $count
  103. //求给定大于等于2的整数的连续质数序列 
  104. //埃拉托色尼筛选法 
  105. function getList($num) { 
  106.     $a = array(); 
  107.     $a = array(); 
  108.     for($i = 2; $i <= $num$i++) { 
  109.         $a[$i] = $i
  110.     } 
  111.     for$i = 2; $i <= floor( sqrt($num) ); $i++ ) { 
  112.         if($a[$i] != 0) { 
  113.             $j = $i * $i
  114.             while($j <= $num) { 
  115.                 $a[$j] = 0; 
  116.                 $j = $j + $i
  117.             } 
  118.         } 
  119.     } 
  120.     $p = 0; 
  121.     for($i = 2; $i <= $num$i++) { 
  122.         if($a[$i] != 0) { 
  123.             $L[$p] = $a[$i]; 
  124.             $p++; 
  125.         } 
  126.     } 
  127.     return $L
  128. ///////////////////////////////////// 
  129. //test 
  130. $time_start  =  microtime_float (); 
  131. //echo ojld(60, 24);       //0.0000450611 seconds 
  132. //echo baseDefine(60, 24); //0.0000557899 seconds 
  133. echo baseSchool(60, 24);   //0.0003471375 seconds 
  134. $time_end  =  microtime_float (); 
  135. $time  =  $time_end  -  $time_start ; 
  136. echo '<br>' . sprintf('%1.10f'$time) . 'seconds'

希望本文所述对大家的php程序设计有所帮助。

Tags: php计算最大公约数

分享到: