最近刷牛客网编程题的时候，遇到一个题
输入一个整数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
