Leetcode之PHP版题目解析(204. Count Primes)



2019-3-29 期五  

 Leetcode之PHP版题目解析(189. Rotate Array)

eb9bf1ac278aea98544b4af9a2a7d767.png


给定一个整数n,返回不大于它的素数的个数。(0和1不是素数)


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

我们先来看一段恐怖的代码,它的思路就是先定义一个额外的数组,只要当前数组中不存在这个数,我们把当前数存入数组并设置为素数,计数器加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;
  }


Github整理地址:https://github.com/wuqinqiang/leetcode-php

吴亲库里 has written 76 articles

情绪只是对自己无能的愤怒

积分:3717 等级:P7 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?