1. 质数和合数是针对所有大于 $1$ 的 “自然数” 来定义的（所有小于等于1的数都不是质数）。

2. 所有小于等于 $1$ 的整数既不是质数也不是合数.

3. 质数的判定——试除法

• $“d\space|\space n”$代表的含义是 $d$ 能整除 $n$ ，（这里的 $“|”$ 代表整除）

• 一个合数的约数总是成对出现的，如果 $d|n$ ，那么 $(n/d)|n$，因此我们判断一个数是否为质数的时候，只需要判断较小的那一个数能否整除 $n$ 就行了，即只需枚举 $d<=(n/d)$，即 $d*d<=n,d<=sqrt(n)$就行了。

• $sqrt(n)$ 这个函数执行的时候比较慢.

  bool is_prime(int x)
  {
      if (x < 2) return false;
      for (int i = 2; i <= x / i; i ++ )
          if (x % i == 0)
              return false;
      return true;
  }

4. 分解质因数——试除法（算数基本定理）

算数基本定理：任何一个大于 $1$ 的自然数 $N$ ，如果 $N$ 不为质数，那么 $N$ 可以唯一分解成有限个质数的乘积 $N=P_1^{a1}P_2^{a2}P_3^{a3}......P_n^{an}$，这里 $P_1<P_2<P_3......<P_n$ 均为质数，其中指数 $a_i$ 是正整数。

• 特别要注意——分解质因数与质因数不一样，分解质因数是一个过程，而质因数是一个数.

• 一个合数分解而成的质因数最多只包含一个大于 $sqrt(n)$ 的质因数（反证法，若 $n$ 可以被分解成两个大于 $sqrt(n)$ 的质因数，则这两个质因数相乘的结果大于 $n$ ，与事实矛盾）

• 当枚举到某一个数 $i$ 的时候，$n$ 的因子里面已经不包含 $[2,i-1]$ 里面的数（已经被除干净了），如果 $n\%i==0$，则 $i$ 的因子里面也已经不包含 $[2,i-1]$ 里面的数，因此每次枚举的数都是质数。

• 质因子（质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

• 两个没有共同质因子的正整数称为互质。因为 $1$ 没有质因子，$1$ 与任何正整数（包括 $1$ 本身）都是互质。

• 只有一个质因子的正整数为质数。

  void divide(int x)
  {
      for (int i = 2; i <= x / i; i ++ )
          if (x % i == 0)
          {
              int s = 0;
              while (x % i == 0) x /= i, s ++ ;
              cout << i << ' ' << s << endl;
          }
      if (x > 1) cout << x << ' ' << 1 << endl; // 大于sqrt(n)的数
      cout << endl;
  }

5. 筛质数（朴素筛法）

• 步骤：把 $[2,n-1]$ 中的所有的数的倍数都标记上，最后没有被标记的数就是质数.
• 原理：假定有一个数 $p$ 未被 $[2,p-1]$ 中的数标记过，那么说明，不存在 $[2,p-1]$ 中的任何一个数的倍数是 $p$ ，也就是说 $[2,p-1]$ 中不存在 $p$ 的约数，因此，根据质数的定义可知：$p$ 是质数.
• 调和级数:当 $n$ 趋近于正无穷的时候，$1/2+1/3+1/4+1/5+…+1/n=\ln{n}+c$（ $c$ 是欧拉常数，约等于 $0.577$ 左右）
• 时间复杂度：约为 $O(nlogn)$（注：此处的 $log$ 特指以 $2$ 为底）

6. 埃氏筛(稍加优化版的筛法)

• 质数定理：$1～n$ 中有 ${\large \frac{n}{\ln{n}}}$个质数.

• 步骤：在朴素筛法的过程中只用质数项去筛.

• 时间复杂度：$O(nlog(logn))$。

  int primes[N], cnt;     // primes[]存储所有素数
  bool st[N];         // st[x]存储x是否被筛掉

  void get_primes(int n)
  {
      for (int i = 2; i <= n; i ++ )
      {
          if (st[i]) continue;
          primes[cnt ++ ] = i;
          for (int j = i + i; j <= n; j += i)
              st[j] = true;
      }
  }

7. 线性筛

• 若$n\approx10^6$，线性筛和埃氏筛的时间效率差不多，若 $n\approx10^7$，线性筛会比埃氏筛快了大概一倍。

• 核心：$1～n$ 内的合数 $p$ 只会被其最小质因子筛掉。（算数基本定理）

• 原理：$1～n$ 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的.
• 枚举到 $i$ 的最小质因子的时候就会停下来，即 if (i % primes[j] == 0) break;
• 当 i % primes[j] != 0时，primes[j] 一定小于 $i$ 的最小质因子，primes[j] 一定是 primes[j]*i 的最小质因子.
• 当 i % primes[j] == 0 时，primes[j] 一定是 $i$ 的最小质因子，而 primes[j] 又是 primes[j] 的最小质因子，因此 primes[j] 是 primes[j]*i的最小质因子.

  int primes[N], cnt;     // primes[]存储所有素数
  bool st[N];         // st[x]存储x是否被筛掉

  void get_primes(int n)
  {
      for (int i = 2; i <= n; i ++ )
      {
          if (!st[i]) primes[cnt ++ ] = i;
          // j < cnt 不必要，因为 primes[cnt - 1] = 当前最大质数
          // 如果 i 不是质数，肯定会在中间就 break 掉
          // 如果 i 是质数，那么 primes[cnt - 1] = i，也保证了 j < cnt
          for (int j = 0; primes[j] <= n / i; j ++ )
          {
              st[primes[j] * i] = true;
              if (i % primes[j] == 0) break;
          }
      }
  }