[PHP知识库] PHP7 求质数的二种算法实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> PHP知识库 -> PHP7 求质数的二种算法实现 -> 正文阅读

[PHP知识库]PHP7 求质数的二种算法实现

试除法

function findPrimes1(int $max = 100): array
{
  // 用于存储所有质数的结果数组
  $primes = [2];

  // 查找范围[3, max] 并略过所有偶数
  for ($n = 3; $n <= $max; $n += 2) {
    foreach ($primes as $p) {
      if ($n % $p === 0) {
        // 质数只能被1和其自身整除
        break;
      } else if ($p >= sqrt($n)) { // 只需要检验至n的开方，减少运算量
        // 质数存入结果数组
        $primes[] = $n;
        break;
      }
    }
  }

  return $primes;
}

筛选法

function findPrimes2(int $max = 100): array
{
  // 下标用于筛选运算的数组
  $nums = array_fill(0, $max, 0);
  unset($nums[0], $nums[1]);

  for ($n = 2; $n <= $max; ++$n) {
    // 已筛去的非质数，略过
    if (!isset($nums[$n])) {
      continue;
    }

    // 通过加法运算来筛去非质数，运算效率比试除法更高
    for ($i = $n + $n; $i <= $max; $i += $n) {
      unset($nums[$i]);
    }
  }
  
  return array_keys($nums);
}