P4-统计素数个数-埃筛法

//统计素数个数
//素数：只能被1和自身整除的自然数，0、1除外
public class P4 {
    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }
 
    //非素数（合数）   12 = 2 * 6
    //埃筛法
    /*
        假设找到2是素数，那么让他倍增，即4、6、8、10....都不是素数
        所以当遍历到4的时候，就可以跳过，减少判断次数
    * */
    public static int eratosthenes(int n) {
 
        //todo n太大的时候还能这样玩吗？
        boolean[] isNotPrime = new boolean[n];     //默认false，代表素数，is not素数吗，false，就是素数
 
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isNotPrime[i]) {
                count++;
 
                //j+=i就是倍增，2i、3i、4i、5i....
//                for (int j = 2 * i; j < n; j += i) {       //j 合数的标记位
//                    isNotPrime[j] = true;
//                }
 
                //需要优化，出现相同的遍历标记
                //i=2，4、6、8、10、12...都已经标记了
                //然后i=3，6、9、12...又再次标记
                //从i*i开始标记即可，前面的已经会被更之前的标记过了
                //即i=2，4、6、8、10、12...已经标记了
                //然后i=3，只需要从9开始标记，虽然后面还是会有重复的（如12），只是减少前面的遍历次数（如6），后面的遍历属于未知
                //todo 感觉还是能再优化
                for (int j = i * i; j < n; j += i) {       //j 合数的标记位
                    isNotPrime[j] = true;
                }
            }
        }
 
        return count;
    }
}