因数

分解

若 $a$ 为 $n$ 的因子, 则 $n/a$ 也为 $n$ 的因子

此法可将时间复杂度压缩到 $O(\sqrt N)$

const int n = 100;

std::vector<int> v;
for(int i = 2; i * i <= n; i++) {
    if(n % i == 0) {
        v.push_back(i);
        if(i != n / i) {
            v.push_back(n / i);
        }
    }
}

python

import math

v = []
for i in range(2, math.sqrt(x)):
    if n % i == 0:
        v.append(i)
        if i != (n / i):
            v.append(v)

最大公约数 gcd

typedef long long ll;

ll gcd(ll a, ll b){
    return b == 0 ? a : gcd(b, a % b);
}

C++ algorithm 库, 内置有__gcd(a, b)函数求最大共约数

积性函数

$f(mn) = f(m) \times f(n), \forall gcd(m, n) = 1$

最小公倍数 lcm

$lcm(a, b) = \frac{a*b}{gcd(a, b)}$

typedef long long ll;

// 先除再乘避免溢出
ll lcm(ll a, ll b){
    return a / gcd(a, b) * m;
}

上篇markdown使用

下篇质数