使用埃筛法解决“统计素数个数”问题

题目：统计N以内的素数
素数：只能被1和自身整除的数，0、1除外

解法2：埃氏筛
利用合数的概念(非素数)，素数 * N必然是合数，因此可以从2开始遍历，将所有的合数做上标记。

将合数标记为true，j = i * i 从 2 * i 优化而来，系数2会随着遍历递增（j += i，相当于递增了系数2），
每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i 必然会遍历到这两个因子
当2递增到大于根号n时，其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n、实际
上在 i 递增的过程中已经计算过了，i 实际上就相当于根号n
例如：n = 25 会计算以下
2 * 4 = 8
3 * 4 = 12
但实际上8和12已经标记过，在n = 17时已经计算了 3 * 4，2 * 4

package od;

/**
 * 埃氏筛选法统计素数个数
 * 利用合数的概念(非素数)，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记
 * 原文地址：https://www.codernav.com/2786.html
 */
public class Odtest07 {
    public static void main(String[] args) {
        int count = eratosthenes(100);
        System.out.println(count);
    }

    public static int eratosthenes(int n) {
        boolean[] isPrime = new boolean[n];//false代表素数
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                ans += 1;
                for (int j = i * i; j < n; j += i) {//j就是合数的标记位
                    isPrime[j] = true;
                }
            }
        }
        return ans;
    }
}