埃氏筛

埃氏筛全称埃拉托斯特尼筛法，主要用于寻找一定范围内所有的质数
基本思想：这种方法的基本思想是从 2 开始，首先找到 2 的所有倍数并标记为非质数，然后找到下一个未被标记的数（即质数），再找到它的所有倍数并标记为非质数，以此类推。这种方法的时间复杂度是 O(n log log n)，空间复杂度是 O(n)。

欧拉筛（线性筛）

区别：欧拉筛在标记倍数时，对其重复标记进行了优化，例如：3的4倍是12，会被标记为合数，2的6倍也是12，也会被标记一次，欧拉筛则是对此处进行了优化，从而提高效率。欧拉筛的时间复杂度是 O(n)。
实现思路
1. 新建一个数组status，将除了0,1以外的所有状态置为true，代表默认都是质数
2. 新建一个数组primes，用来存放所有的质数
3. 从2开始到n循环，如果是质数，就添加到primes数组中，然后遍历primes，得到其的倍数为合数，在status中置为false
4. 统计primes的长度即可
图示

欧拉筛

解释
1. 第一步和第二步：从2开始遍历，2为true，代表为质数，加入primes数组中，然后遍历primes，将其与i相乘，得到4，则4为合数，进行标记。
2. 第三步：i为3，status为true，为质数，加入primes数组中，遍历primes，2 × 3 = 6，3 × 3 = 9，将6和9标记为合数
3. 第四步：i为4，status为false，为合数，不用加入数组，遍历primes，2 × 4 = 8，将8标记为合数，3 × 4 = 12，应该也将12进行标记，但是如果此时标记了，那么在后面i为6，2 × 6 = 12还是会标记一次，所以这里添加了条件判断 if (i % prime == 0) break; 防止重复标记
4. 之后的步骤则重复上述步骤，是质数，加入数组，再遍历数组，是合数，直接遍历数组。

代码

public int countPrimes(int n) {
     // 记录当前时间
    long start = System.currentTimeMillis();
     if (n < 2) {
         return 0;
     }
     ArrayList<Integer> primes = new ArrayList<>();
     boolean[] status = new boolean[n + 1];
     Arrays.fill(status, true);
     // 0和1不是质数
     status[0] = false;
     status[1] = false;
   
     for (int i = 2; i < n; i++) {
         // 如果i是质数
         if (status[i]) {
             primes.add(i);
         }
         // 遍历素数集合
         for(int pj : primes) {
             // 得到的合数pj * i出界，结束遍历
             if(pj * i > n) {
                 break;
             }
             status[pj * i] = false;
             // 如果pj是i的最小素因子，结束遍历，防止重复标记合数
             if(i % pj == 0) {
                 break;
             }
         }
     }
     System.out.println(System.currentTimeMillis() - start);
     return primes.size();

埃氏筛

欧拉筛（线性筛）

回溯法