leetcode-top面试题计数质数

浅浅的花香味﹌ 2021-11-27 06:14 262阅读 0赞

**题目**  
统计所有小于非负整数 n 的质数的数量。  
示例:  
输入: 10  
输出: 4  
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

**思路**  
采用厄拉多塞筛法  
介绍：该算法在寻找素数时，采用了一种与众不同的方法：先将 2－N 的各数放入表中，然后在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；现在既未画圈又没有被划去的第一个数是 5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。  
这时，表中画了圈的以及未划去的那些数正好就是小于 N 的素数。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**代码实现**

public static int countPrimes(int n) {
            boolean[] isNotPrime = new boolean[n];
            int count = 0;
            for(int i=2;i<n;i++){
                if(!isNotPrime[i]){
                    isNotPrime[i] = false;
                    count++;
                    for(int j=1;i*j<n;j++){//遍历小于n的i的倍数
                        isNotPrime[i*j]=true;
                    }
                }
            }
            return count;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]

作者：ba-zha-hei-2  
链接：[https://leetcode-cn.com/problems/two-sum/solution/e-la-duo-sai-shai-fa-by-ba-zha-hei-2/][https_leetcode-cn.com_problems_two-sum_solution_e-la-duo-sai-shai-fa-by-ba-zha-hei-2]  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20211126/7e6ba03de27d47688a0375fc78ce56de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20211126/511b885e1dd747fbb9c1ec8d1666221e.png
[https_leetcode-cn.com_problems_two-sum_solution_e-la-duo-sai-shai-fa-by-ba-zha-hei-2]: https://leetcode-cn.com/problems/two-sum/solution/e-la-duo-sai-shai-fa-by-ba-zha-hei-2/