将一个大于等于 2 的整数分解为若干个质因数之积的过程为分解质因数。

透过分解质因数的算法，不仅可以求出一个数的质因数，还可以计算积性函数在给定数上的值。

朴素算法

从小到大遍历 n 的可能因数即可。

令变量 i 遍历 \left[2, \sqrt{n} \right] 中的整数，若 i \mid n，则说明 i 是 n 的一个质因数，同时反复令 n = n / i，直到 n 不能被 i 整除为止。

map<unsigned, unsigned> factorize(unsigned n)
{
    map<unsigned, unsigned> indices;
    for (unsigned i = 2; i * i <= n; i++)
    {
        unsigned idx = 0;
        while (n % i == 0)
        {
            n /= i;
            idx++;
        }
        indices[i] = idx;
    }
    if (n != 1)
    {
        indices[n] = 1;
    }
    return map;
}

若已经预先筛得 \left[2, \sqrt{n} \right] 中的质因数，则可以降低枚举复杂度：

vector<unsigned> primes;
map<unsigned, unsigned> factorize(unsigned n)
{
    map<unsigned, unsigned> indices;
    for (size_t i = 0; primes[i] * primes[i] <= n; i++)
    {
        unsigned p = primes[i], idx = 0;
        while (n % p == 0)
        {
            n /= p;
            idx++;
        }
        indices[p] = idx;
    }
    if (n != 1)
    {
        indices[n] = 1;
    }
    return map;
}

筛法

质数筛

Eratosthenes 筛

在 Eratosthenes 筛中，每个数都会被自己的每一个质因数筛一次，依据此可以预处理出每个数的质因数。

Euler 筛

首先使用 Euler 筛预处理 x \in [1, n] 的最小质因数 m_x，则可以递归地将 x 的质因数转为 \frac{x}{m_x} 的质因数再添加一个 m_x。由于每次除法 x 至少减半，Euler 筛预处理的时间和空间复杂度都是 O(n)，但是对单个数分解质因数的复杂度降为 O(\log n)。