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

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

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

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

Tags: php计算最大公约数

分享到：