小议分解质因数函数的实现
作者：James Zhu ([email protected])
创建日期：2018-03-08
概述
这个问题来源于一个游戏 Human Resource Machine，通过这个游戏，我们可以粗浅地了解编程语言底层的实现逻辑。
其实任何一个函数，乃至乘法除法，都是用最基础的加/减/if/jump堆砌出来的。因此，编程与数学之间是有着非常紧密的联系的，只是大部分时候，我们所用的高级语言，已经用预先定义的函数直接实现了，无需普通开发者去了解其中的数学逻辑。
本文就以分解质因数为例，了解数学在编程中发挥的作用。
定义
质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。
每个合数都可以写成几个质数（也可称为素数）相乘的形式，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。例如：
64: 2 × 2 × 2 × 2 × 2 × 2
65: 5 × 13
66: 2 × 3 × 11
67: 67
实现
分解质因数，要从最小的质数除起，一直除到结果为质数为止。
function demo1($n) {
$factors = array();
for($i = 2; $i <= $n; $i++) {
while($n % $i == 0) {
$n /= $i;
$factors[] = $i;
}
}
return $factors;
}
这是最简单的实现，只包含了8行代码。但是，这个函数的效率是非常低效的。从2开始循环到10000，全部处理运行了3.1秒。
首先，如果一个数如果2不是它的质因子，那么4,6,8,...都不是它的质因子。因此上述循环中包含了n/2次的冗余处理。因此，我们将偶数从循环中剥离出来，实现如下。
function demo2($n) {
$factors = array();
while($n % 2 == 0) {
$n /= 2;
$factors[] = 2;
}
for($i = 3; $i <= $n; $i += 2) {
while($n % $i == 0) {
$n /= $i;
$factors[] = $i;
}
}
return $factors;
}
通过上述实现，我们可以发现，先将一个数不断除以2直到变为一个奇数，再从3开始，每次累加2进行整除，最后得到质因子分解式。从2开始循环到10000，全部处理运行了1.5秒。比起demo1，效率已经提高了1倍！那么还有没有优化空间呢，答案是有的。
假设，一个合数可以表达为 a × b 的形式，且 a <= b，那么 。
这里需要理解一下，a和b都是给定整数的质因子，那么 a × b = b × a。以65为例，a = 5, b = 13，在循环至 a = 13 之前，5 × 13 这个组合早已在 a = 5 时被消化了。
当 a = b 时，a的取值范围达到了极限值 ，因此
。
根据以上分析，再次优化函数，实现如下。
function demo3($n) {
$factors = array();
while($n % 2 == 0) {
$n /= 2;
$factors[] = 2;
}
$sqrt = floor(sqrt($n));
for($i = 3; $i <= $sqrt; $i += 2) {
while($n % $i == 0) {
$n /= $i;
$factors[] = $i;
}
}
if($n > 1) {
$factors[] = $n;
}
return $factors;
}
从2开始循环到10000，全部处理运行了0.5秒。比起demo2，效率再次提高了2倍！
因此，我们可以发现，编程仅仅实现功能是不够的，这只是一个开始。在实际应用过程中，我们可以对代码进行不断的优化。当然，优化的逻辑可能是数学的原理，也可能是业务的优化。总之，去除冗余的循环、冗余的代码，是我们提升效率的核心。
彩蛋
从2开始循环到10000的Python函数实现。
import math
def demo4(n):
factors = []
while n % 2 == 0:
n = n / 2
factors.append(2)
sqrt = math.floor(math.sqrt(n))
i = 3
while i <= sqrt:
while n % i == 0:
n = n / i
factors.append(i)
i = i + 2
if n > 1:
factors.append(int(n))
return factors
j = 2
while j <= 10000:
print(j,':',demo4(j))
j = j + 1