求[0, N)的素数个数

0，1不算，2算

解题思路：

• 最简单的是暴力求解，两次循环
• 埃式筛选法，使用一个数组作为标记数组。默认全部为素数（此方法必须保证首个数字是质数，即从2开始）

/**
 * 统计N以内的素数[0, N)
 * 解题思路：暴力求解（很多场景都可以用暴力求解，但是并不优雅）；艾塞法
 */
public class Src02 {
    public static void main(String[] args) {
        System.out.println(bf(12));
        System.out.println(screening(12));
    }

    // 暴力求解
    public static int bf(int N) {
        int count = 0;
        for (int i = 2; i < N; i++) {
            if(isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    // 判断是否为素数
    public static boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) {  // 必须是 <=
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }

    // 埃筛法 利用和数必然存在一组[2,n]的数，相乘等于n
    public static int screening(int n) {
        boolean[] list = new boolean[n];    // 默认false；这里使用false表示素数
        int count = 0;
        for(int i = 2; i < n; i++) {    // 遍历 [2~n)
            if(!list[i]) {  // 从2开始乘以一个数
                count++;
                for (int j = i * i; j < n; j += i) {    // 条件比较巧妙
                    list[j] = true;
                }
            }
        }
        return count;
    }
}