204. 计数质数（算法思维系列）

川长思鸟来 2023-10-05 20:31 39阅读 0赞

#### 204. 计数质数 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

统计所有小于非负整数 n 的质数的数量。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

大体思路比较简单，主要是明白

*  首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。
 *  然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。

然后还有一个就是`i 不需要遍历到 n，而只需要到 sqrt(n) 即可。为什么呢，我们举个例子，假设 n = 12。`

12 = 2 × 6
    12 = 3 × 4
    12 = sqrt(12) × sqrt(12)
    12 = 4 × 3
    12 = 6 × 2

## 代码 ##

class Solution {
        
        public int countPrimes(int n) {
        
            boolean[] isPrim = new boolean[n];
            // 将数组都初始化为 true
            Arrays.fill(isPrim, true);
    
    //这里i*i相当于判断一个数是否是素数的 isPrime 函数，由于因子的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了
            for (int i = 2; i*i < n; i++) {
        
                if (isPrim[i])
                    // i 的倍数不可能是素数了
                    for (int j = 2 * i; j < n; j += i)
                        isPrim[j] = false;
            }
    
    
            int count = 0;
            for (int i = 2; i < n; i++)
                if (isPrim[i]) count++;
    
            return count;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210226150447774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70