PHP函数怎样写一个判断是否为质数的函数 PHP函数质数判断的入门编写教程​

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 . " 是质数。";
} else {
  echo $num . " 不是质数。";
}

$number - 1

sqrt($number)

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;
}

6k ± 1

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;
    }

    // 进行 k 次测试
    for ($i = 0; $i < $k; $i++) {
        $a = rand(2, $n - 2);
        $x = bcpowmod($a, $r, $n); // 使用 bcmath 扩展处理大数

        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; // 继续外层循环
        }

        return false; // 不是质数
    }

    return true; // 有很大概率是质数
}

bcmath

bcpowmod

bcmath

$k

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);