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为质数
  9. for ($i = 3; $i <= $n; $i += 2) { // 偶数不是质数,步长可以加大
  10. $sqrt = intval(sqrt($i)); // 求根号n
  11. for ($j = 3; $j <= $sqrt; $j += 2) { // i是奇数,当然不能被偶数整除,步长也可以加大。
  12. if ($i % $j == 0) {
  13. break;
  14. }
  15. }
  16. if ($j > $sqrt) {
  17. array_push($prime, $i);
  18. }
  19. }
  20. return $prime;
  21. }

测试代码:

  1. $res = primeNumber(100);
  2. // 输出:[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]
  3. echo json_encode($res);