求n以内的质数PHP版

PHP , ,

答案

质数筛选定理:

  1. n不能够被小于等于根号n的任何质数整除,则n是一个质数
  2. 除了2,其他偶数都不是质数
/**
 * 求n以内的质数
 * @param $n int 质数的最大范围
 * @return array 质数集合
 */
function primeNumber($n)
{
    $prime = array(2);                          // 2为质数

    for ($i = 3; $i <= $n; $i += 2) {           // 偶数不是质数,步长可以加大
        $sqrt = intval(sqrt($i));               // 求根号n
        for ($j = 3; $j <= $sqrt; $j += 2) {    // i是奇数,当然不能被偶数整除,步长也可以加大。
            if ($i % $j == 0) {
                break;
            }
        }
        if ($j > $sqrt) {
            array_push($prime, $i);
        }
    }

    return $prime;
}

测试代码:

$res = primeNumber(100);

// 输出:[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]
echo json_encode($res);

解析

第一个定理涉及到最小质因数的概念,我们先来看看什么是质因数。

所谓质因数(或称素因子)在数论里是指能整除给定正整数的素数

例如:

6 = 2 * 3,那么236的质因数,而2是最小的那个,所以2是最小质因数

140 = 2 * 2 * 5 * 7,那么2、5、7就是140的质因数,注意质因数都是质数2是最小质因数。

任何大于等于3的正整数,只要它不是质数,那肯定是合数,而所有合数都能分解成2个以上的质数的乘积。

说明:01既不是质数也不是合数,2是最小的质数。

理解了以上概念,我们再返回来证明答案中的第一条定理:n不能够被小于等于根号n的任何质数整除,则n是一个质数

这个定理等价于,n的最小质因数肯定小于或等于n的平方根。

证明:假如n的最小质因数x大于n的平方根,那n肯定还有一个质因数y,而y要大于等于x更大于n的平方根,那么xy就要大于n了,就矛盾了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

昵称 *