素数

素数

找出0到n以内的素数,0和1除外

解题：

方式一（暴力法）：

function isPrime($i)
{
    for ($j = 2; $j < $i; $j++) {
        if ($i % $j === 0) {
            return false;
        }
    }
    return true;
}

function getPrimeCount($n) {
    $count = 0;
    for ($i = 2; $i < $n; $i++) {
        if(isPrime($i)) {
            $count++;
        }
    }
}

优化:开根号，只要小于$i开平方根之后的值中，存在能够整除$i的即不是素数

举例：

$i = 6; 开根号 为 2.44....，其中2能够整除6，所以为素数

$i = 15; 开根号 为 3.87....，其中3能够整除15，所以为素数

$i = 36; 开根号 为 6, 其中2能够整除15，所以为素数

规律

6 ，有 23 和 32 这两个整除结果

15， 有35 和 53 这两个整除结果

36， 有218、312、49、66、94、123、18*2

其实超过根号$i的可整除结果，是以$i的开根树对位的。

这样我们就可以优化，如11，我们只需要判断2和3满不满足就行了，2、3都不能整除，就是素数了。

function isPrime($i)
{
    for ($j = 2; $j * $j < $i; $j++) {
        if ($i % $j === 0) {
            return false;
        }
    }
    return true;
}

方式二：埃氏筛选

素数求解中最出名的算法了，通过一个额外的空间，来标记素数

例子：

$prime = [false,false,.......];

$n = 15

第一次循环：2

内部循环:

$j = 2*2 = 4不为素数

$j += $i = 6不为素数

$j += $i = 8不为素数

$j += $i = 10不为素数

$j += $i = 12不为素数

$j += $i = 14不为素数

$j += $i = 16 > 15跳出循环

这样一来，我们就通过一个数，筛掉了一批数据，下次我们到达这个数的时候就可以直接进行判断

第二次循环：3

内部循环:

$j = 3*3 = 9不为素数

$j += $i = 12不为素数

$j += $i = 15 = 15跳出循环

以此类推

function getPrimeCount($n)
{
    $original_arr = array_fill(0,$n, false);
    $count = 0;
    for ($i = 2; $i < $n; $i++) {
        if (!$original_arr[$i]) {
            $count++;
            for ($j = $i * $i; $j < $n; $j += $i) {
                $original_arr[$j] = true;
            }
        }
    }
    return $count;
}