统计 n 以内的素数个数

统计 n 以内的素数个数。比如，n = 100 时，素数个数有 25  个。

思路：利用 埃筛法。从第一个质数 2 开始，找到倍数是 2 的倍数的合数。再从下一个质数 3 找起来，所有 3 的 倍数的合数。直到 n 的平方根为止。

 

public Main{

    public void findNumOfPrime(int n){
        boolean[] isPrime = new boolean[n+1];
        for(int i=1;i<n+1;i++){
            isPrime[i] = true;
        }
        int count = 0;
        for(int i=2;i<n+1;i++){
            if(i*i>n){
                break;
            }
            if(isPrime[i]) {
                for (int k = i; k * i <= n; k++) {
                    isPrime[i*k] = false;
                }
            }
        }
        for(int i=2;i<n+1;i++){
            if(isPrime[i]){
                count++;
            }
        }
        System.out.println(count);


    }


}