當前位置:首頁 > PHP教程 > php高級應用 > 列表

PHP實現的分解質因數操作示例

發布:smiling 來源: PHP粉絲網  添加日期:2018-11-15 09:48:38 瀏覽: 評論:0 

本文實例講述了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. $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. fenjie_num(390, $zhishu); 

運行結果:

2

3

5

13

Tags: PHP分解質因數

分享到:

福利彩票25选5开奖结果