質(zhì)數(shù)的定義

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

實(shí)現(xiàn)思路

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

第一種算法

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

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function 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 / 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)不會break退出，則執(zhí)行完畢，$i會繼續(xù)+1，即最后$i = floor($value / 2) + 1
        // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會break退出，$i不會繼續(xù)+1，即最后$i <= floor($value / 2)
        if ($value != 1 && $i > floor($value / 2)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

### 第二種算法

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

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function 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)不會break退出，則執(zhí)行完畢，$i會繼續(xù)+1，即最后$i = floor($value / $i) + 1
        // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會break退出且$i不會繼續(xù)+1，即最后$i <= floor($value / $i)
        if ($value != 1 && $i > floor($value / $i)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

第三種算法

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

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function 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)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！