LeetCode - 204 Count Primes

Question

题目大意

筛选 0~n ( [0，n) ) 之间的素数个数。

解析

如果用经典的判断素数，时间复杂度为 O(n*sqrt(n)) ，会超时。

于是使用经典的 埃拉托斯特尼筛法（有动图演示) 。

超时:

class Solution {
    //TLE
    public boolean isPrime(int nums){
        if(nums == 0 || nums == 1)
            return false;
        for(int i = 2; i <= (int)Math.sqrt(nums); i++){ // <= not < 
            if(nums%i == 0)
                return false;
        }
        return true;
    }
    
    public int countPrimes(int n) {
        int res = 0;
        for(int i = 0; i < n; i++){
            if(isPrime(i))
                res++;
        }
        return res;
    }
}

正解:

class Solution {
    public int countPrimes(int n) {
        if(n < 3)
            return 0;
        int res = 0;
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime,true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2; i < n; i++){
            if(isPrime[i]){
                res++;
                for(int j = 2*i; j < n; j+=i) //筛选
                    isPrime[j] = false;
            }
        }
        return res;
    }
}