Leetcode之PHP版题目解析（204. Count Primes）

Created 6 years ago by 吴亲库里, Updated 5 years ago Revision #1 2933 views 0 likes 0 collects

2019-3-29 星期五开始吧

上一题链接 Leetcode之PHP版题目解析（189. Rotate Array）

题目描述

给定一个整数n，返回不大于它的素数的个数。（0和1不是素数）

题目案例

案例中给定10，返回4个，分别是2，3，5，7.

题目分析

我们先来看一段恐怖的代码，它的思路就是先定义一个额外的数组，只要当前数组中不存在这个数，我们把当前数存入数组并设置为素数，计数器加1，然后再把他所有的倍数值出来作为数组的非素数（倍数不可能是素数），由于我这的判断条件是<n,但是我们已经求的每个数的倍数，相当于我们做了多余的操作，随着数字越大，我们的效率就越低，直接超时。

这段恐怖代码

xxxxxxxxxx
 
/**
     * @param Integer $n
     * @return Integer
     */
    function countPrimes($n) {     
         $array=[];
         $nums=0;
        for($i=2;$i<$n;$i++) {
           if($array[$i]===NULL){
              $array[$i]=1;
              $nums++;
              $y=2;
             while($i*$y<$n) {
                 $array[$i*$y]=0;
                 $y++;
             }
         }     
     }
        return $nums;
  }

改进

正如我说的，我们应该标记已经确定不是素数的数字，我们不需要再重复的去处理，避免高额的调用。

具体实现

xxxxxxxxxx
 
/**
     * @param Integer $n
     * @return Integer
     */
    function countPrimes($n) {     
        $is_primes=[];
        for($i=2;$i<$n;$i++) {
            $is_primes[$i]=true;
        }
        for($i=2;$i*$i<$n;$i++) {
            if($is_primes[$i]===false) continue;
            for($j=$i*$i;$j<$n;$j +=$i) {
                $is_primes[$j]=false;
            }
        }
      
        $count=0;
        for($i=2;$i<$n;$i++) {
            if($is_primes[$i]) $count++;
        }
        return $count;
  }