素数：只能被1和自身整除的自然数，0、1除外

1、暴力算法

  1. public static int bf(int n) {
  2.         if (n == 0 || n == 1) {
  3.             return 0;
  4.         }
  5.         int count = 0;
  6.         for (int i = 2; i < n; i++){
  7.             count += isPrime(i) ? 1 : 0;
  8.         }
  10.         return count;
  11.     }
  13.     private static boolean isPrime(int x) {
  14.         // 这里为什么使用i*i <= x?
  15.         // 因为这里 i <= 根号x 即可，因为相乘是相对的
  16.         // 12=2*6,12=3*4,12=4*3,12=6*2，中间的分界点就是根号12
  17.         // 用根号12又不好表示，直接用 i*i <= x 就既可以达到目的，又方便表示
  18.         for (int i = 2; i * i <= x; i++) {
  19.             if (x % i == 0) {
  20.                 return false;
  21.             }
  22.         }
  23.         return true;
  24.     }

2、埃氏筛选

利用合数的概念（非素数），素数*n必然是一个合数，因此可以从2开始便利，将所有的合数做一个标记，在后面筛选时直接跳过这些已经标记过的合数

    public static int eratosthenes(int n) {
        boolean[] isPrimes = new boolean[n];// false代表素数
        int count = 0;
        for (int i = 2; i < n; i++) {
            // 将合数给标记出来，在后面查找时，排除这些合数，减少了排查的次数
            if (!isPrimes[i]) {
                count++;
                for (int j = i * i; j < n; j+=i) { // j是合数的标记位
                       isPrimes[j] = true;
                }
            }
        }
        return count;
    }

1、首先创建一个boolean数组，数组长度是传进来的值，我们将合数标记为true，素数标记为false

2、j=ii 是从 j=i2 优化而来，系数2会随着遍历递增（j+=i，就相当于系数2自加了一次，—> j=in，n++）
例如：
for (int j = i 2; j < n; j+=i) {}
等价于
for(int x=2,int j = i x; j < n; j = i (++x)) {}
下面的方法的可读性好一些，但是不够简洁

当i=2时 当i=3时 当i=5时 当i=7时 当i=11时
2*2 3*2 5*2 7*2 11*2
2*3 3*3 5*3 7*3 11*3
2*4 3*4 5*4 7*4 11*4
2*5 3*5 5*5 7*5 11*5
2*6 3*6 5*6 7*6 11*6
2*7 3*7 5*7 7*7 11*7
2*8 3*8 5*8 7*8 11*8
2*9 3*9 5*9 7*9 11*9
2*10 3*10 5*10 7*10 11*10
2*11 3*11 5*11 7*11 11*11

从上面结果可以看出，当i=5时，52,53在前面已经被标记过了，54因为4是合数，可以被分解为22，则会在210被标记。所以直接从ii开始即可，这样其实也会有重复标记的，但是重复标记的会少很多。从ii后，会补上前面标记不出来的i(比i大的素数）的值。