分解质因数

分解质因数引入

给定一个正整数 $N \in \mathbf{N}_{+}$ ，试快速找到它的一个非平凡因数。

考虑朴素算法，因数是成对分布的，的所有因数可以被分成两块，即 $[2, \sqrt N]$ 和 $[\sqrt N+1,N)$ 。只需要把 $[2, \sqrt N]$ 里的数遍历一遍，再根据除法就可以找出至少两个因数了。这个方法的时间复杂度为 $O(\sqrt N)$ 。

当 $N\ge10^{18}$ 时，这个算法的运行时间我们是无法接受的，希望有更优秀的算法。一种想法是通过随机的方法，猜测一个数是不是的因数，如果运气好可以在 O(1) 的时间复杂度下求解答案，但是对于 $N\ge10^{18}$ 的数据，成功猜测的概率是 $\frac{1}{10^{18}}$ , 期望猜测的次数是 $10^{18}$ 。如果是在 $[2,\sqrt N]$ 里进行猜测，成功率会大一些。我们希望有方法来优化猜测。

朴素算法

最简单的算法即为从 $[2, \sqrt N]$ 进行遍历。

1 2 3 4 5 6 7 8 910111213vectorint> breakdown(int N) {vectorint> result;for (int i = 2; i * iN; i++) {if (N % i == 0) {// 如果 i 能够整除 N，说明 i 为 N 的一个质因子。while (N % i == 0) N /= i;result.push_back(i);}}if (N != 1) {// 说明再经过操作之后 N 留下了一个素数result.push_back(N);}return result;} 1 2 3 4 5 6 7 8 910def breakdown(N):result = []for i in range(2, int(sqrt(N)) + 1):if N % i == 0:# 如果 i 能够整除 N，说明 i 为 N 的一个质因子。while N % i == 0:N //= iresult.append(i)if N != 1:# 说明再经过操作之后 N 留下了一个素数result.append(N)return result

我们能够证明 result 中的所有元素即为 N 的全体素因数。

证明 result 中即为

的全体素因数

首先考察 N 的变化。当循环进行到 i 结束时，由于刚执行结束 while(N % i == 0) N /= i 部分，i 不再整除 N。而且，每次除去一个因子，都能够保证 N 仍整除。这两点保证了，当循环进行到 i 开始时，N 是的一个因子，且不被任何小于 i 的整数整除。

其次证明 result 中的元素均为的因子。当循环进行到 i 时，能够在 result 中存入 i 的条件是 N % i == 0，这说明 i 整除 N，且已经说明 N 是的因子，故而有 i 是的因子。当对 i 的循环结束时，若 N 不为一，也会存入 result。此时它根据前文，也必然是的一个因子。

其次证明 result 中均为素数。我们假设存在一个在 result 中的合数，则必然存在 i 不超过 $\sqrt K$ ，满足 i 是 K 的一个因子。这样的不可能作为循环中的某个 i 存入 result，因为第一段已经说明，当循环到时，N 不被任何小于的 i 整除。这样的也不可能在循环结束后加入，因为循环退出的条件是 i * i > N，故而已经遍历完了所有不超过 $\sqrt K$ 的 i，而且据上文所说，这些 i 绝不能整除目前的 N，亦即。

最后证明，所有的素因子必然出现在 result 中。不妨假设是的一个素因子，但并没有出现在 result 中。根据上文的讨论，不可能是循环中出现过的 i。设 i 是退出循环前最后的 i，则 i 严格小于，而退出循环后的 N 不被之前的 i 整除，故而整除 N。所以最后的 N 大于一，则根据前文所述，它必然是素数，则 N 就等于，必会在最后加入 result，与假设矛盾。

值得指出的是，如果开始已经打了一个素数表的话，时间复杂度将从 $O(\sqrt N)$ 下降到 $O(\sqrt{\frac N {\ln N}})$ 。去筛法处查阅