深入算法: 如何快速求一个数的所有因子数?

2022-12-02 11:34 作者:StepfenShawn 0人读过 | 我要投稿

如何编写一个求一个数所有因子的程序呢? 假设这个数是2000, 相信大家很快就可以写出如下代码:

上面程序可以正确地得出答案，该程序的时间复杂度为O(n), 2000次循环对cpu来说也只是几毫秒的事情，但如果将 n 扩大为一个16位的整数，计算机就可能要算上一天了。。。

如何进行优化呢，这就要开始研究因子数的数学性质了! 下面我们就来从0开始证明一个数与其因子数存在什么性质:

先假设自然数 $N$ , 我们要求出它所有因子的集合 $%5Cleft%5C%7B%201%2C%20x1%2C%20x2%2C%20...%2C%20N%20%5Cright%5C%7D%20$ ，我们需要证明两个命题成立即可:

命题1: 因子是成对出现的：如果自然数 $N$ 存在一个因子 $x1$ , 那么必然存在另一个因子 $x2$ 使得 $x1%20*%20x2%20%3D%20N$ (注意这里如果 N 是平方数的话 $x1$ 可以等于 $x2$ )。

证明: 已知 $x1%20%7C%20N$ , 要证明该命题成立我们只需证明 $%5Cfrac%7BN%7D%7Bx1%7D%20%20%7C%20N%20$ 即可, 由 $x1%20%7C%20N$ , 我们知 N 可以分解成一个数字 $x1$ 和另一个数字 $m$ , 又因为 $x2%20%3D%20%5Cfrac%7BN%7D%7Bx1%7D%20%20%3D%20m$ , 所以 $%20x2%20%7C%20N$ 。

题外话: 上述证明只是从直观上来出发，如何用反证法来证明呢，可以先假设另一个数字 $m$ 不能整除 N, 那么最后会推出 $x1$ 是不能整除 N 的, 而与条件 $x1%20%7C%20N$ 产生矛盾, 所以 $m$ 一定会整除 $N$ .

(这个方法的证明思路就放在这里了，过程交给读者了)

命题2:因数是成对出现的(上面已证明)，一个小于等于算数平方根，另外一个大于等于算数平方根

证明: 我们利用反证法证明简单地这个命题，假设我们找到了一个因子 $x1$ 小于 $%5Csqrt%7BN%7D%20$ , 如果存在另一个因子 $x2$ 也小于 $%5Csqrt%7BN%7D%20$ , 那么 $x1%20*%20x2%20%3C%20N$ , 那么因子 $x1$ 与其成对的因子必然不是 $x1$ 。假设我们找到了一个因子 $x1$ 大于 $%5Csqrt%7BN%7D%20$ , 如果存在另一个因子 $x2$ 也大于 $%5Csqrt%7BN%7D%20$ , 那么 $x1%20*%20x2%20%3E%20N$ , 那么因子与其成对的因子必然不是 $x2$ 。所以一对因子唯一的可能就是一个小于等于 $%5Csqrt%7BN%7D%20$ ，另外一个大于等于 $%5Csqrt%7BN%7D%20$ 。