LeetCode204——计数质数

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/count-primes/description/

题目描述：

知识点：素数

思路一：挨个判断[2, n - 1]范围内的数是否是素数

时间复杂度是O(n ^ 1.5)。空间复杂度是O(1)。

JAVA代码：

class Solution {
    public int countPrimes(int n) {
        int result = 0;
        for(int i = 2; i < n; i++){
            if(isPrime(i)){
                result++;
            }
        }
        return result;
    }
    private boolean isPrime(int n){
        if(n == 1){
            return false;
        }
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}

LeetCode解题报告：

思路二：埃氏筛

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

时间复杂度是O(nloglogn)。空间复杂度是O(n)。

JAVA代码：

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

LeetCode解题报告：