PHP算法之求1000万之内素数的个数（10秒以内）

最近刷牛客网编程题的时候，遇到一个题
输入一个整数n(1≤n≤10000000)，输出n以内素数的个数。时间限制：1秒 空间限制：32768K

这个题需求很简单，难就难在时间限制1秒，内存限制32M

网络上求素数个数的方法有很多，大部分都是非PHP语言写的，转成PHP语言之后就会有点问题，要么是速度太慢，要么就是内存溢出，毕竟在一些运算上面PHP是没办法和C语言相比的。琢磨了很长时间也没办法实现1秒之内求出1000万之内素数的个数，最好的在10秒以内，差了一个数量级。

1540006579798.jpg

推算

10以内的素数 ：

排除掉[2,3,5] 的整倍数[2,3,4,5,6,8,9,10]，结果=10-count([4,6,8,9,10])+count([2,3,5])-1=4

30以内的素数：

排除掉 [2,3,5,7] 的整倍数[2,3,5,6,7,8,9,10,12,14...]，结果=30-count([2,3,5,6,7,8,9,10,12,14...])+count([2,3,5,7])-1=10

总结一下

求n以内素数的个数
1，求出一个数组$prime_arr，这个数组是一个素数的集合，从2开始循环生成素数，当生成的素数大于n的开方的时候，停止，这时得到这个数组$prime_arr;
2，循环n，如果值v能被数组$prime_arr中任何一个数整除，则把v这个数排除掉
3，统计没有被排除的数的个数，再加上$prime_arr的个数，再减去1，就是结果了
代码如下

<?php
fscanf(STDIN,'%d',$a);
$t1=microtime(true);
$arr=prime_arr($a);
$n=$a-1;//素数个数，排除法
for ($i=2;$i<=$a;$i++){
    foreach ($arr as $v){
        if($i % $v ==0){
            $n--;
            break;
        }
    }
}
$t2=microtime(true);
echo $n+count($arr)."\t".round($t2-$t1,3)."\n";

/**
 * 下一个素数
 */
function next_prime($i){//下一个质数
    while (true){
        $i++;
        if($i==2){
            return $i;
        }elseif ($i<2){
            continue;
        }
        $is=true;
        for($j=2;$j<=sqrt($i);$j++){
            if($i % $j ==0){
                $is=false;
            }
        }
        if($is){
            return $i;
        }
    }
}

/**
 * 作为除数的素数数组
 */
function prime_arr($a){
    if($a<=1){
        return [];
    }
    $arr=[];
    $prime=0;
    while ($prime<=sqrt($a)){
        $prime=next_prime($prime);
        $arr[]=$prime;
    }
    return $arr;
}

运行代码，输入1000000 ，返回664579 9.522
一共664579个素数，耗时9.5秒，没办法通过测试

1538925008095.jpg