- 素数判定：$\sqrt{n}$算法，直接枚举所有小于根号n的数字，取模判定
- 素数筛法：思路很简单，把所有素数的倍数标记为非素数即可。可能需要long long。
- 质因数分解：一句话描述，从2开始到根号n，逮到一个因数就死命除掉
  ```c
  vector<int> prime_factor(int n){
    vector<int> retval;
    for (int i = 2; i * i <= n; ++ i){
      if (n % i == 0) {
        retval.push_back(i);
        while(n % i == 0) n /= i;
      }
    }
    if (n != 1) retval.push_back(i);
  }
  ```
- 快速幂：
  ```c
  int fpow(int a, int b) { // a^b
    int ans = 1;
    while (b) {
      if (b & 1) ans *= a;
      a*= a;
      b >>= 1;
    }
  }
  ```
- GCD辗转相除，没啥好说的，其实也可以用编译器函数
  ```c
  int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
  inline int gcd(int a, int b) {
    while (b) {
      int tmp = a;
      a = b;
      b = tmp % b;
    }
  }
  ```
	- 另外，对于 C++14，我们可以使用自带的 `__gcd(a,b)` 函数来求最大公约数。而对于 C++ 17，我们可以使用 [`<numeric>`](https://en.cppreference.com/w/cpp/header/numeric) 头中的 [`std::gcd`](https://en.cppreference.com/w/cpp/numeric/gcd) 与 [`std::lcm`](https://en.cppreference.com/w/cpp/numeric/lcm) 来求最大公约数和最小公倍数。