204.md

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

2019-03-29 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

✏️题目实例

​ **案例1给定[1,2,3,4,5,6,7],k是3，返回[5,6,7,1,2,3,4],也就是说k是多少就把数组的后k位转移到数组的前k位，形成新的数组.**

✏️题目分析

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

      /**
         * @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;
      }

---

✏️解法二

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

   /**
      * @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;
   }

联系

​