php 质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他[因数]的自然数。

<?php
require_once 'init.php';

xhprof_enable(XHPROF_FLAGS_NO_BUILTINS);
$num = 2000;
$a1 = getPrimes($num);
$a2 = getPrimes2($num);

var_dump(strcmp($a1,$a2));


print_r(xhprof_disable());die;
var_dump($a1);
var_dump($a2);

/**
 * 常规遍历算法
 * @param int $num
 * @return string
 */
function getPrimes(int $num) {
    $digit = 2;
    $count = 0;
    $primes = [];
    while ($count < $num) {
        $i = 2;
        $is_prime = true;
        while ($i < $digit) {
            if ($digit % $i++ == 0) {
                $is_prime = false;
                break;
            }
        }
        if ($is_prime) {
            $count++;
            $primes[] = $digit;
        }
        $digit++;
    }
    return join(',', $primes);
}

/**
 * 最大值调节算法
 * @param int $num
 * @return string
 */
function getPrimes2(int $num) {
    $digit = 2;
    $count = 0;
    $primes = [];
    while ($count < $num) {
        $i = 2;
        $is_prime = true;
        $max = $digit;
        while ($i < $max) {
            if ($digit % $i == 0) {
                $is_prime = false;
                break;
            }
            $i++;
            $max = ceil($digit / $i) + 1;
        }
        if ($is_prime) {
            $count++;
            $primes[] = $digit;
        }
        $digit++;
    }
    return join(',', $primes);
}

function checkPrime($num) {
    $i = 2;
    $max = $num;
    while ($i < $max) {
        if ($num % $i == 0) {
            return false;
        }
        $i++;
        $max = ceil($num / $i);
    }
    return true;
}

function checkPrime2($num) {
    $i = 2;
    while ($i < $num) {
        if ($num % $i == 0) {
            return false;
        }
        $i++;
    }
    return true;
}

运行结果：

# 说明两个算法结果是一致的
int(0)
getPrimes()函数用了 1.367318s；getPrimes2()函数只用了 0.162182s
近10倍差距，而且随着计算数量的增加，这个差距还会继续增大
# 
Array
(
    [main()==>getPrimes] => Array
        (
            [ct] => 1
            [wt] => 1367318
        )

    [main()==>getPrimes2] => Array
        (
            [ct] => 1
            [wt] => 162182
        )

    [main()] => Array
        (
            [ct] => 1
            [wt] => 1529593
        )

)

简单说明一下

如何判断11是一个质数？

如果 11/2 不能整除，那么就说明 11 除以 11/2 ~ 10 也一定不能整除
如果 11/2 不能整除，而 11/3 有可能被整除，但 11/3 + 1 肯定是不能被整除的，所以 11/3 + 1 ~ 10 必然也不能被整除，而这一段可以不遍历。