PHP 求n以内的质数

答案

质数筛选定理：

  • n不能够被不大于根号n的任何质数整除，则n是一个质数

  • 除了2，其他偶数都不是质数

  1. /**
  2.  * 求n以内的质数
  3.  * @param $n int 质数的最大范围
  4.  * @return array 质数集合
  5.  */
  6. function primeNumber($n)
  7. {
  8.     $prime = array(2);                          // 2为质数
  10.     for ($i = 3; $i <= $n; $i += 2) {           // 偶数不是质数，步长可以加大
  11.         $sqrt = intval(sqrt($i));               // 求根号n
  12.         for ($j = 3; $j <= $sqrt; $j += 2) {    // i是奇数，当然不能被偶数整除，步长也可以加大。
  13.             if ($i % $j == 0) {
  14.                 break;
  15.             }
  16.         }
  17.         if ($j > $sqrt) {
  18.             array_push($prime, $i);
  19.         }
  20.     }
  22.     return $prime;
  23. }

测试代码：

  1. $res = primeNumber(100);
  3. // 输出：[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
  4. echo json_encode($res);