【算法】统计素数个数 - 埃筛法

题目

传入一个数字，统计小于这个数字的素数个数。

原理

素数只能被1和它本身整除，所以小的数能够通过乘法计算出来的数都不是素数。埃筛法就是不断地用小的数做乘法标记出哪些数不是素数，从而减少遍历次数。

代码

    public static void main(String[] args) {
        int count = countPrime(100);
        System.out.println(count);
    }

    private static int countPrime(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                for (int j = 2 * i; j < n; j+=i) {
                    notPrime[j] = true;
                }
            }
        }
        return count;
    }