Leetcode刷题java之204. 计数质数（一天一道编程题之第二十一天）-蒲公英云

Leetcode刷题java之204. 计数质数（一天一道编程题之第二十一天）

向右看齐 2023-07-13 12:25 84阅读 0赞

执行结果：

通过

显示详情

执行用时 :14 ms, 在所有 Java 提交中击败了80.36% 的用户

内存消耗 :39.5 MB, 在所有 Java 提交中击败了16.23%的用户

题目：

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

创建一个boolean数组，用排除法，倍数不是质数。

优化：外层循环到开方，内层循环从平方开始

代码：

class Solution {
    public int countPrimes(int n) {
        boolean[] isprime=new boolean[n];
        for(int i=2;i*i<=n;i++)
        {
            if(!isprime[i])
            {
                for(int j=i*i;j<n;j+=i)
                {
                    isprime[j]=true;
                }
            }
        }
        int result=0;
        for(int i=2;i<n;i++)
        {
            if(!isprime[i])
            {
                result++;
            }
        }
        return result;
    }
}