LEETCODE 204. Count Primes 解题思路分析

题目大意:

计数质数

统计所有小于非负整数 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=204

解题思路分析:

本题暴力解法是从2循环到n,查看每一个数是否是质数,如果是,返回结果加一。而判断是否为质数,我们只能查看其是否能被2到n-1中的某个数整除,这样一来二层循环的计算压力会非常大,因此我们可以考虑采用排除法。

首先建立一个bool型数组,长度为n,查看哪些数字不是质数。我们从2开始循环,2本身是一个最小的质数,因此,所有2的倍数一定不是质数,因此,我们可以将2的倍数都排除掉,即在bool数组中,将下标为2的倍数位均设为true。之后看数字3,此时如何判定3是否为质数呢?我们知道3如果是合数(不是质数),那么他一定是某个质数相乘得到的,而小于它的质数只有2,并且我们已经排除掉了2的所有倍数,因此我们只要判断bool型数组中index为3的位置是否为true即可,如果是true,说明3是合数,反之如果是false,说明3是质数。当3是质数时,再将3的所有倍数排除掉,以此类推,直到n,我们就能排除掉所有的非质数。这时,只要统计一下bool数组中质数的数量(为false的位)即可。

另外这里有一处可以优化的地方,其实我们不用从2遍历到n,遍历到根号n即可,因为大于根号n的数字如果是非质数,它肯定是包含在小于根号n质数的倍数里。

实现代码:

public int countPrimes(int n) {
    // 排除法统计非质数
    boolean[] isNotPrime = new boolean[n];
    for(int i=2;i*i<n;i++){
        if(isNotPrime[i]) continue;
        for(int j=2*i;j<n;j+=i){
            isNotPrime[j]=true;
        }
    }
    int res=0;
    for(int i=2;i<n;i++){
        if(!isNotPrime[i]) res++;
    }
    return res;
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 74.00% of Java online submissions for Count Primes.

Memory Usage: 39 MB, less than 5.66% of Java online submissions for Count Primes.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-204-count-primes-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。