数论

class PrimeNumber {
  // O(sqrt(N)) 质数判断
  public static boolean isPrime(int n) {
   	if (n < 2) return false;
    
    for (int i = 2; i <= n / i; i++) {
      if (n % i == 0) return false;
    }
    
    return true;
  }
  
  // O(sqrt(N)) 质因数分解
  private static void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
      if (n % i == 0) {
      	int s = 0;
        while (n % i == 0) {
          n /= i; s++;
        }
        System.out.println(i + " " + s);
      }
    }
    if (n ! = 1) System.out.println(n + " " + 1);
  }
  
  // [2, N] 中包含多少个质数
  // O(NloglogN) 埃氏筛法
  final static int N = 1000010;
  static int idx = 0;
  final static int[] q = int[N];
  final static boolean[] st = new boolean[N];

  private static void getPrimeIndex(int n) {
    for (int i = 2; i <= n; i++) {
      if (st[i]) continue;
      q[idx++] = i;
      for (int j = i + i; j <= n; j++) st[j] = true;
    }
  }
  
  // O(N) 线性筛法
  private static void getPrimeIndex(int n) {
    for (int i = 2; i <= n; i++) {
      if (!st[N]) q[idx++] = i;
      for (int j = 0; q[j] <= n / i; j++) {
        st[q[j] * i] = true;
        if (i % q[j] == 0) break;
      }
    }
  }
}