leetcode 204. 计数质数

￡神魔★判官ぃ 2022-09-03 02:29 177阅读 0赞

[leetcode链接][leetcode]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70]

两种方法 暴力+埃筛法

# 1.暴力法 #

class Solution { 
        public int countPrimes(int n) { 
            //暴力解决 如果n在 1到 n-1内都没有能被整除的 那么就是素数
            int count =0;
            for(int i=2;i<n;i++){ //2 3 4 5 6 7 8 9
                count+=isPrime(i)?1:0;
            }
            return count;
        }
        //判断某个数是不是素数
        public boolean isPrime(int x){ //2 3 4 5 6 7 8 9
            //从2开始 2 3 4 5 6 7 8 9
            //进阶 我们只需要比较 到根号x即可 后面的就是反着来的 如 2*6=6*2 3*4=4*3
            //这时候就要取到等号 如 100=10*10 不能忽略了
            for(int j=2;j*j<=x;j++){ 
                //如果是素数 每次取余 都应该会有余数
                if(x%j==0) return false;
            }
            //遍历完毕 都有余数 说明为素数
            return true;
        }
    }

# 2.埃筛法 #

class Solution { 
        //埃筛法 先假设n=10
        public int countPrimes(int n) { 
            //先默认所有数都为素数 而后某个数 如 2*3 2*4 2*5 之类的数 提前标志为true
            boolean[] isPrime=new boolean[n];
            //计数器
            int count=0;
            //先从2开始
            for(int i=2;i<n;i++){ 
                //因为默认都是false 去反才能进入判断
                if(!isPrime[i]){ 
                    count++;
                    //防止溢出
                    if((long)i*i<n){ 
                        //第一次循环 j=2*2=4 
                        //第二次循环 j=4+2=6 
                        //第三次循环 j=6+2=8
                        //之后就跳出 然后在进来 j=3*3=9
                        for(int j=i*i;j<n;j+=i){ 
                            isPrime[j]=true;
                        }
                    }
                }
            }
            //上面筛选出4个 10个减去头尾减去4=4
            return count;
        }
    }

[leetcode]: https://leetcode-cn.com/problems/count-primes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM1MzUwNw_size_16_color_FFFFFF_t_70]: /images/20220829/8f7ac35993904e7c8de81c2639d06128.png