質(zhì)數(shù)又稱素?cái)?shù)。一個(gè)大于1的自然數(shù)，除了1和它自身外，不能整除其他自然數(shù)的數(shù)叫做質(zhì)數(shù)；否則稱為合數(shù)。

循環(huán)所有可能的備選數(shù)字，然后和中間數(shù)以下且大于等于2的整數(shù)進(jìn)行整除比較，如果能夠被整數(shù)，則肯定不是質(zhì)數(shù)，相反，就是質(zhì)數(shù)。

這也是最可能先想到的，也就是直接和備選數(shù)的中間數(shù)去比較，算法源碼如下：

/** * 獲取所有的質(zhì)數(shù) * @param array $arr * @return arrayfunction get_prime_number($arr = []) { // 質(zhì)數(shù)數(shù)組 $primeArr = []; // 循環(huán)所有備選數(shù) foreach ($arr as $html' target='_blank'>value) { // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較 for ($i = 2; $i = floor($value / 2); $i++) { // 能夠整除，則不是質(zhì)數(shù)，退出循環(huán) if ($value % $i == 0) { break; // 被除數(shù)$j比備選數(shù)的中間數(shù)大的則為質(zhì)數(shù) // 這樣判斷的依據(jù)： // 假如備選數(shù)為質(zhì)數(shù)，則內(nèi)層的for循環(huán)不會(huì)break退出，則執(zhí)行完畢，$i會(huì)繼續(xù)+1，即最后$i = floor($value / 2) + 1 // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會(huì)break退出，$i不會(huì)繼續(xù)+1，即最后$i = floor($value / 2) if ($value != 1 $i floor($value / 2)) { $primeArr[] = $value; return $primeArr;}

### 第二種算法

認(rèn)真的來(lái)說(shuō)的話，這也不算是另外一種算法，只是對(duì)于第一種的稍微點(diǎn)點(diǎn)優(yōu)化，及中間最大數(shù)的優(yōu)化，縮小比較范圍，算法源碼如下：

/** * 獲取所有的質(zhì)數(shù) * @param array $arr * @return arrayfunction get_prime_number($arr = []) { // 質(zhì)數(shù)數(shù)組 $primeArr = []; // 循環(huán)所有備選數(shù) foreach ($arr as $value) { // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較 for ($i = 2; $i = floor($value / $i); $i++) { // 能夠整除，則不是質(zhì)數(shù)，退出循環(huán) if ($value % $i == 0) { break; // 被除數(shù)$j比備選數(shù)的中間數(shù)大的則為質(zhì)數(shù) // 這樣判斷的依據(jù)： // 假如備選數(shù)為質(zhì)數(shù)，則內(nèi)層的for循環(huán)不會(huì)break退出，則執(zhí)行完畢，$i會(huì)繼續(xù)+1，即最后$i = floor($value / $i) + 1 // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會(huì)break退出且$i不會(huì)繼續(xù)+1，即最后$i = floor($value / $i) if ($value != 1 $i floor($value / $i)) { $primeArr[] = $value; return $primeArr;}

這個(gè)的話也是對(duì)于第二種的優(yōu)化，即，直接從完整數(shù)組中刪除所有不是質(zhì)數(shù)的數(shù)即可，算法源碼如下：

/** * 獲取所有的質(zhì)數(shù) * @param array $arr * @return arrayfunction get_prime_number_three($arr = []) { // 質(zhì)數(shù)數(shù)組 $primeArr = $arr; // 循環(huán)所有備選數(shù) foreach ($primeArr as $key = $value) { if ($value == 1) { unset($primeArr[$key]); continue; // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較 for ($i = 2; $i = floor($value / $i); $i++) { // 能夠整除，則不是質(zhì)數(shù)，從數(shù)組中刪除且退出循環(huán) if ($value % $i == 0) { unset($primeArr[$key]); break; // 重置數(shù)組索引返回 return array_values($primeArr);}

比如，求1-100的所有質(zhì)數(shù)

// 所有備選數(shù)數(shù)組$numberArr = range(1, 100, 1);// 獲取備選數(shù)中的所有質(zhì)數(shù)$primeNumberArr = get_prime_number($numberArr);// 輸出打印print_r($primeNumberArr);

又比如，求指定數(shù)組中的所有質(zhì)數(shù)

// 所有備選數(shù)數(shù)組$numberArr = [11, 22, 33, 66, 77, 3, 8, 10, 99];// 獲取備選數(shù)中的所有質(zhì)數(shù)$primeNumberArr = get_prime_number($numberArr);// 輸出打印print_r($primeNumberArr);

以上就是php如何判斷一個(gè)數(shù)是否是質(zhì)數(shù)的三種方法的詳細(xì)內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。