素数判定

四大判定法

1. 试除法

   boolean prime(int v) {
       if(v < 2) return false;
       if(v == 2) return true;
       if(v % 2 == 0) return false;
       for(int i = 3;i * i <= v;i += 2) {
           if(v % i == 0) return false;
       }
       return true;
   }

2. 埃氏筛

   [详解](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)

   /***
    * 
    * @param n 求[2 - n]范围内的素数
    * @return boolean数组，false则为素数
    */
   boolean[] eratosthenes(int n) {
       int g = (int) Math.sqrt(n);
       boolean[] b = new boolean[n + 1];
       for(int i = 2;i <= n;++i) {
           if(!b[i]) {
               if(i > g) break;
               for(int k = i * i;k <= n;k += i) {
                   b[k] = true;
               }
           }
       }
       return b;
   }

3. 欧拉筛

   static List<Integer> ps = new ArrayList<>();
   static boolean[] b = new boolean[10001];
   static {
       b[0] = b[1] = true;
       for(int i = 2;i <= 10000;i++) {
           if(!b[i]) ps.add(i);
           for(int p : ps) {
               if(i * p > 10000) break;
               b[i * p] = true;
               if(i % p == 0) break;
           }
       }
   }

4. Miller-Rabin