给定整数 n​​ ,返回 所有小于非负整数 n​​ 的质数的数量 。

示例 1:

<pre><strong>输入:</strong>n = 10
<strong>输出:</strong>4
<strong>解释:</strong>小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
</pre>

示例 2:

<pre><strong>输入:</strong>n = 0
<strong>输出:</strong>0
</pre>

示例 3:

<pre><strong>输入:</strong>n = 1
<strong>输出</strong>:0
</pre>

暴力算法

当然也是显而易见的超出时间限制啦!!!

class Solution {
    public int countPrimes(int n) {
        if(n<=2)return 0;
        int count = 0;
        for(int i = 2; i<n; ++i){
            count += isPrime(i)?1:0;
        }
        return count;
    }
    private static boolean isPrime(int x){
        for(int i = 2; i*i<=x; ++i){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
}

当然可以提炼出一个判断是否为素数的方法

判断是否为素数的方法

private static boolean isPrime(int x){
        for(int i = 2; i*i<=x; ++i){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }

注意:

注意这个i*i<=x,其实就是i<=根号x,可以减少循环的次数,提高效率。

埃氏筛法

核心思想:
首先,使用一个数组来存储每个数字的标记,fasle代表是质数,本质上判断从2到n-1的范围内是否有可以整除的数字,找到一个质数之后,就将这个质数的两倍,三倍,四倍。。。只要小于n,都标记为合数,再依次执行即可。

巧妙的是,找到二倍,三倍,四倍的方法

 for(int j = 2*i; j<n; j+=i){
                    isPrime[j] = true;
                }
class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        int count = 0;
        // (2,n-1)的范围内
        for(int i = 2; i<n; ++i){
            if(!isPrime[i]){
                count++;
                // 2倍,三倍,4倍。。。
                for(int j = 2*i; j<n; j+=i){
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }
}

埃氏筛法的优化

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

主要是针对这里优化

  for(int j = i*i; j<n; j+=i){
                    isPrime[j] = true;
                }

针对这张图,红线已经计算过一次了,但是橙线还要计算一次。

但是对于很大的数字,i*i很有可能会超过int的类型范围。