获取质数数组

思路:
暴力解法,遍历每一个数,将这个数与2开始的数字取模,如果为0则不为质数

代码:
function getPrime()
{
    // 记录质数的数组
    $p = [2, 3];

    for ($i = 4; $i < self::MAX_N; $i++) {
        $isPrime = true;
        for ($j = 2; $j <= sqrt($i); $j++) {
            if ($i % $j === 0) {
                // 如果能整除,则不为质数
                $isPrime = false;
                break;
            }
        }

        if ($isPrime) {
            $p[] = $i;
        }
    }

    return $p;
}

思路:
线性筛法,记录质数的下标,质数*n (n>=2)的值也不是质数

代码:
function getPrime($num)
{
    if ($num < 2) {
        return [];
    }
    // 记录质数下标的数组
    $isPrime    = array_fill(0, $num, true);
    $isPrime[0] = $isPrime[1] = false;
    // 记录质数的数组
    $primes = [];
    for ($i = 2; $i < $num; $i++) {
        if ($isPrime[$i]) {
            // 下标为true,记录质数
            $primes[] = $i;
        }

        foreach ($primes as $prime) {
            if ($i * $prime >= $num) {
                // 超过指定范围,break
                break;
            }

            // 指定不为质数的下标
            $isPrime[$prime * $i] = false;
            if ($i % $prime === 0) {
                // 防止重复设定质数下标
                break;
            }
        }
    }

    return $primes;
}