LogSeq/pages/简单数学算法.md

• 素数判定：$\sqrt{n}$算法，直接枚举所有小于根号n的数字，取模判定
• 素数筛法：思路很简单，把所有素数的倍数标记为非素数即可。可能需要long long。
• 质因数分解：一句话描述，从2开始到根号n，逮到一个因数就死命除掉

  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);
  }
  

• 快速幂：

  int fpow(int a, int b) { // a^b
    int ans = 1;
    while (b) {
      if (b & 1) ans *= a;
      a*= a;
      b >>= 1;
    }
  }
  

• GCD辗转相除，没啥好说的，其实也可以用编译器函数

  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> 头中的 std::gcd 与 std::lcm 来求最大公约数和最小公倍数。