小议分解质因数函数的实现

作者：James Zhu ([e-mail])

创建日期：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

外部资源

• 在线 LaTeX 公式编辑器