您好,登錄后才能下訂單哦!
使用PHP怎么分解質(zhì)因數(shù)?針對這個問題,這篇文章詳細介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
思路:
如果要計算$num的質(zhì)數(shù),則至少收集$num以內(nèi)的質(zhì)數(shù)數(shù)組,判斷$num是否在質(zhì)數(shù)數(shù)組里:
如果否,則判斷當(dāng)前質(zhì)數(shù)$zhishu[$i]是否能再次將整除后的數(shù)整除,如果能,則質(zhì)數(shù)數(shù)組“游標(biāo)”不移動(還讓當(dāng)前質(zhì)數(shù)$zhishu[$i]對被整除后的數(shù)取模)
如果不能(再次將整除后的數(shù)整除),則用下一個質(zhì)數(shù)(讓$i++)去測試是否整除。如果否($num在質(zhì)數(shù)數(shù)組里),則表示$num本身就是個質(zhì)數(shù),直接echo之。(思路看得糊涂的話,直接看代碼吧)
首先:用一個函數(shù)收集一定范圍內(nèi)的質(zhì)數(shù)放到數(shù)組里返回。(把1從質(zhì)數(shù)里剔除,從2開始算質(zhì)數(shù)),代碼和注釋如下:
//得到1000以內(nèi)的質(zhì)數(shù) function get_zhishu($num=1000){ $num = floor($num); $zhishu = array(); //先得到1000以內(nèi)的質(zhì)數(shù) for($i=1; $i<=$num; $i++){ $flag = true; //當(dāng)flag為false時表示該數(shù)不是素數(shù) for($j=2; $j<$num; $j++){ //$j從2開始,因為除數(shù)為1時,肯定能整除 if($i>$j){ //$j如果比$i還大,取??隙ú粸?,沒有比較的意義 $mod = $i%$j; if($mod == 0 ){ //當(dāng)除數(shù)$j為$i以內(nèi)時,如果取模為0,表示該數(shù)不是素數(shù) $flag = false; } } } if($flag){ array_push($zhishu, $i);//如果$flag為真,則$i是質(zhì)數(shù) } } array_shift($zhishu); //把1從質(zhì)數(shù)數(shù)組中剔除 return $zhishu; } $zhishu = get_zhishu(1000); //得到1到1000之內(nèi)的質(zhì)數(shù)
然后:從質(zhì)數(shù)數(shù)組中,挨個取出(從最小的質(zhì)數(shù)開始)符合條件(能被整除)的質(zhì)數(shù)。代碼和注釋如下:
/** * @param int $num 要分解的質(zhì)數(shù) * @param array $zhishu 1000以內(nèi)的質(zhì)數(shù)數(shù)組 * @param int $i 相當(dāng)于質(zhì)數(shù)數(shù)組的"游標(biāo)" * @author misaka去年夏天 */ function fenjie_num($num, $zhishu, $i=0){ if(!is_int($num) || $num<0){ exit('請輸入正整數(shù)!'); } if(in_array($num, $zhishu)){ //如果該數(shù)為質(zhì)數(shù),則echo之 echo $num,'<br />'; }else{ $ceil = ceil($num/$zhishu[$i]); if($ceil == ($num/$zhishu[$i])){ echo $zhishu[$i],'<br />'; if($ceil%$zhishu[$i]!=0){ //如果當(dāng)前質(zhì)數(shù)還能被$ceil整除,則繼續(xù)用該質(zhì)數(shù)(不用$i++),比如90分解為2、3、3、5,否則讓$i++再遞歸 $i++; } fenjie_num((int)$ceil, $zhishu, $i); }else{ fenjie_num($num, $zhishu, $i+1); //對于99這樣的,不是質(zhì)數(shù),但也沒第一次被整除的,用下一個質(zhì)數(shù)($i++)測試它 } } } fenjie_num(390, $zhishu);
運行結(jié)果:
2
3
5
13
關(guān)于使用PHP怎么分解質(zhì)因數(shù)問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。