$\Huge\color{orchid}{点击此处获取更多干货}$

试除法

一个正整数的约数指的是能整除它的所有正整数，对于任意正整数$x$来说，判断其是否为质数，以及求出它的所有约数，都可以用试除法，从2遍历到$\left \lfloor \sqrt[]{x} \right \rfloor $，遇上能整除的数$i$时，判断质数是直接退出，求约数就是将一对约数$\left \{i,x/i \right \}$记录下来。对于完全平方数$x$，遇到$i*i=x$的情况时，只需要记录其中一个即可。

C++ 代码

/**
 * @brief 试除法求所有约数
 * @param x 待求的数
 * @return x的约数（从小到大排列）
 */
vector<int> allFactors(int x) {
    vector<int> factors;
    for (int i = 1; i <= x / i; i++) {          //跟质数判定一样，只循环到sqrt(x)
        if (x % i == 0) {                       //能整除就说明找到了一对约数
            factors.push_back(i);
            if (i != x / i) {                   //除了i=sqrt(x)的情况以外，其余整除的情况都可以产生一对不同的约数
                factors.push_back(x / i);
            }
        }
    }
    sort(factors.begin(), factors.end());       //从小到大排序
    return factors;
}