Leetcode:204. 计数质数

题目描述

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

示例:

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

思路

思路1

统计从2开始到n的所有数进行非质数标记的方法计数

思路2

在思路1的基础上优化迭代，使用$ii$作为边界，因为质数筛法时大于$\sqrt{n}$会被筛选到，同时j设置为$ii$,减少筛选次数

代码

代码1

class Solution {
    public int countPrimes(int n) {
        if (n == 0 || n == 1){
            return 0;
        }
        int result = n;
        int[] dps = new int[n];
        for(int i = 2; i < n; i++){
            for(int j = 2; j*i < n; j++){
                if (dps[i * j] == 1){
                    continue;
                }
                dps[i * j] = 1;
                result -= 1;
            }
        }
        return result - 2;
    }
}

代码2

class Solution {
    public int countPrimes(int n) {
        if (n == 0 || n == 1){
            return 0;
        }
        int result = n;
        int[] dps = new int[n];
        for(int i = 2; i * i < n; i++){
            for(int j = i * i; j < n; j += i){
                if (dps[j] == 1){
                    continue;
                }
                dps[j] = 1;
                result -= 1;
            }
        }
        return result - 2;
    }
}

复杂度分析

思路1时间复杂度

$O(nloglogn)$?

思路1空间复杂度

$O(n)$

思路2时间复杂度

$O(nloglogn)$

思路2空间复杂度

$O(n)$