判斷一個(gè)數(shù)是否為質(zhì)數(shù)的核心是檢查其是否僅能被1和自身整除，1. 使用基礎(chǔ)函數(shù)時(shí)只需循環(huán)到sqrt($number)以減少計(jì)算量；2. 優(yōu)化方法包括排除偶數(shù)并利用6k±1的形式跳過(guò)非質(zhì)數(shù)；3. 對(duì)大數(shù)應(yīng)采用miller-rabin等概率算法結(jié)合bcmath擴(kuò)展提高效率；4. 生成質(zhì)數(shù)數(shù)組可結(jié)合isprime函數(shù)逐個(gè)判斷并存儲(chǔ)，適用于需預(yù)生成質(zhì)數(shù)列表的場(chǎng)景，該方法完整有效。

判斷一個(gè)數(shù)是否為質(zhì)數(shù)，核心在于檢查它除了1和自身之外，是否還能被其他數(shù)整除。一個(gè)簡(jiǎn)單的PHP函數(shù)就能搞定這個(gè)任務(wù)。

function isPrime(int $number): bool {
  if ($number <= 1) {
    return false;
  }

  for ($i = 2; $i <= sqrt($number); $i++) {
    if ($number % $i === 0) {
      return false;
    }
  }

  return true;
}

// 示例用法
$num = 29;
if (isPrime($num)) {
  echo $num . " 是質(zhì)數(shù)。";
} else {
  echo $num . " 不是質(zhì)數(shù)。";
}

PHP判斷質(zhì)數(shù)函數(shù)：如何提高效率？

首先，最直觀的優(yōu)化就是減少循環(huán)次數(shù)。沒(méi)必要一直循環(huán)到

$number - 1

sqrt($number)

立即學(xué)習(xí)“PHP免費(fèi)學(xué)習(xí)筆記（深入）”；

其次，可以排除偶數(shù)。 除了2以外，沒(méi)有偶數(shù)是質(zhì)數(shù)。 所以可以在函數(shù)一開(kāi)始就排除偶數(shù)，然后循環(huán)的時(shí)候每次遞增2。

function isPrimeOptimized(int $number): bool {
  if ($number <= 1) {
    return false;
  }
  if ($number <= 3) {
    return true;
  }
  if ($number % 2 === 0 || $number % 3 === 0) {
    return false;
  }

  for ($i = 5; $i * $i <= $number; $i = $i + 6) {
    if ($number % $i === 0 || $number % ($i + 2) === 0) {
      return false;
    }
  }
  return true;
}

這個(gè)優(yōu)化后的版本，先排除了小于等于1的數(shù)，然后直接處理了2和3這兩個(gè)特殊的質(zhì)數(shù)。 接著，排除了所有能被2或3整除的數(shù)。 最后，循環(huán)只檢查那些不太容易被小質(zhì)數(shù)整除的數(shù)，步長(zhǎng)為6。 為什么是6呢？ 因?yàn)樗匈|(zhì)數(shù)（大于3的）都可以表示成

6k ± 1

PHP質(zhì)數(shù)判斷：如何處理大數(shù)？

即構(gòu)數(shù)智人

即構(gòu)數(shù)智人是由即構(gòu)科技推出的AI虛擬數(shù)字人視頻創(chuàng)作平臺(tái)，支持?jǐn)?shù)字人形象定制、短視頻創(chuàng)作、數(shù)字人直播等。

36

查看詳情

處理大數(shù)時(shí)，簡(jiǎn)單的循環(huán)判斷可能效率非常低。 比如要判斷一個(gè)15位的數(shù)字是不是質(zhì)數(shù)，用前面的方法可能需要幾秒甚至幾分鐘。 這時(shí)候，可以考慮使用一些更高級(jí)的算法，比如 Miller-Rabin 質(zhì)數(shù)測(cè)試。

Miller-Rabin 是一種概率性算法，它不能保證100%準(zhǔn)確，但可以通過(guò)多次測(cè)試來(lái)提高準(zhǔn)確率。 它的基本思想是基于費(fèi)馬小定理和二次探測(cè)定理。

function millerRabin(int $n, int $k = 5): bool {
    if ($n <= 1) return false;
    if ($n <= 3) return true;

    // 找到 (s, r) 使得 n - 1 = 2^s * r (r is odd)
    $s = 0;
    $r = $n - 1;
    while ($r % 2 == 0) {
        $s++;
        $r /= 2;
    }

    // 進(jìn)行 k 次測(cè)試
    for ($i = 0; $i < $k; $i++) {
        $a = rand(2, $n - 2);
        $x = bcpowmod($a, $r, $n); // 使用 bcmath 擴(kuò)展處理大數(shù)

        if ($x == 1 || $x == $n - 1) continue;

        for ($j = 0; $j < $s - 1; $j++) {
            $x = bcpowmod($x, 2, $n);
            if ($x == $n - 1) continue 2; // 繼續(xù)外層循環(huán)
        }

        return false; // 不是質(zhì)數(shù)
    }

    return true; // 有很大概率是質(zhì)數(shù)
}

注意，這個(gè)函數(shù)使用了

bcmath

bcpowmod

bcmath

$k

PHP質(zhì)數(shù)判斷：與數(shù)組結(jié)合的應(yīng)用場(chǎng)景

假設(shè)你需要生成一個(gè)包含前 N 個(gè)質(zhì)數(shù)的數(shù)組。 你可以結(jié)合

isPrime

function generatePrimeArray(int $n): array {
  $primes = [];
  $number = 2;
  while (count($primes) < $n) {
    if (isPrime($number)) {
      $primes[] = $number;
    }
    $number++;
  }
  return $primes;
}

// 示例
$primeArray = generatePrimeArray(10);
print_r($primeArray);

這個(gè)函數(shù)會(huì)從2開(kāi)始，依次判斷每個(gè)數(shù)字是否為質(zhì)數(shù)，如果是，就添加到數(shù)組中，直到數(shù)組包含 N 個(gè)質(zhì)數(shù)為止。 這在一些需要預(yù)先生成質(zhì)數(shù)列表的場(chǎng)景下非常有用，比如密碼學(xué)或者數(shù)論相關(guān)的應(yīng)用。 當(dāng)然，如果 N 很大，你可能需要考慮使用更高效的質(zhì)數(shù)生成算法。

以上就是PHP函數(shù)怎樣寫(xiě)一個(gè)判斷是否為質(zhì)數(shù)的函數(shù) PHP函數(shù)質(zhì)數(shù)判斷的入門(mén)編寫(xiě)教程?的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注php中文網(wǎng)其它相關(guān)文章！