本文实例讲述了PHP实现的分解质因数操作。分享给大家供大家参考，具体如下：

思路：如果要计算$num的质数，则至少收集$num以内的质数数组，判断$num是否在质数数组里：如果否，则判断当前质数$zhishu[$i]是否能再次将整除后的数整除，如果能，则质数数组“游标”不移动（还让当前质数$zhishu[$i]对被整除后的数取模）

如果不能（再次将整除后的数整除），则用下一个质数（让$i++）去测试是否整除。如果否（$num在质数数组里），则表示$num本身就是个质数，直接echo之。（思路看得糊涂的话，直接看代码吧）

首先：用一个函数收集一定范围内的质数放到数组里返回。（把1从质数里剔除，从2开始算质数），代码和注释如下：

1. //得到1000以内的质数 
2. function get_zhishu($num=1000){ 
3.   $num = floor($num); 
4.   $zhishu = array(); 
5.   //先得到1000以内的质数 
6.   for($i=1; $i<=$num; $i++){ 
7.     $flag = true; //当flag为false时表示该数不是素数 
8.     for($j=2; $j<$num; $j++){ //$j从2开始，因为除数为1时，肯定能整除 
9.       if($i>$j){ //$j如果比$i还大，取模肯定不为0，没有比较的意义 
10.         $mod = $i%$j; 
11.         if($mod == 0 ){ //当除数$j为$i以内时，如果取模为0，表示该数不是素数 
12.           $flag = false; 
13.         } 
14.       } 
15.     } 
16.     if($flag){ 
17.       array_push($zhishu, $i);//如果$flag为真，则$i是质数 
18.     } 
19.   } 
20.   array_shift($zhishu); //把1从质数数组中剔除 
21.   return $zhishu; 
22. } 
23. $zhishu = get_zhishu(1000); //得到1到1000之内的质数 

然后：从质数数组中，挨个取出（从最小的质数开始）符合条件（能被整除）的质数。代码和注释如下：

1. /** 
2.  * @param int $num 要分解的质数 
3.  * @param array $zhishu 1000以内的质数数组 
4.  * @param int $i 相当于质数数组的"游标" 
5.  * @author misaka去年夏天 
6.  */ 
7. function fenjie_num($num, $zhishu, $i=0){ 
8.   if(!is_int($num) || $num<0){ 
9.     exit('请输入正整数！'); 
10.   } 
11.   if(in_array($num, $zhishu)){ //如果该数为质数，则echo之 
12.     echo $num,'<br>'; 
13.   }else{ 
14.     $ceil = ceil($num/$zhishu[$i]); 
15.     if($ceil == ($num/$zhishu[$i])){ 
16.       echo $zhishu[$i],'<br>'; 
17.       if($ceil%$zhishu[$i]!=0){ 
18.         //如果当前质数还能被$ceil整除，则继续用该质数(不用$i++)，比如90分解为2、3、3、5，否则让$i++再递归 
19.         $i++; 
20.       } 
21.       fenjie_num((int)$ceil, $zhishu, $i); 
22.     }else{ 
23.       fenjie_num($num, $zhishu, $i+1); //对于99这样的，不是质数，但也没第一次被整除的，用下一个质数($i++)测试它 
24.     } 
25.   } 
26. } 
27. fenjie_num(390, $zhishu); 

运行结果：

2

3

5

13

Tags: PHP分解质因数

分享到：