素数分解

将一个数分解成其组成的因子，也称为素因子分解。给定一个正整数 ，素数分解可以写成

其中 是 个 素因子，每个素因子的阶数为 。每个因子 称为一个 primary。素数分解可以使用 Wolfram 语言中的命令FactorInteger[n] 来执行，该命令返回 对的列表。

通过他发明的 Pratt 证书，Pratt (1975) 成为第一个确定素数分解属于 NP 复杂度类的人。

以下 Wolfram 语言代码可以用于给出数字 的良好排版形式

  FactorForm[n_?NumberQ, fac_:Automatic] :=
    Times @@ (HoldForm[Power[##]]& @@@
      FactorInteger[n, fac])

前几个素数分解（根据定义，数字 1 的素数分解为 "1"）在下表中给出。

	素数分解		素数分解
1	1	11	11
2	2	12
3	3	13	13
4		14
5	5	15
6		16
7	7	17	17
8		18
9		19	19
10		20

n=1, 2, ... 的素数分解中的位数是 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 3, (OEIS A050252)。

一般来说，素数分解是一个难题，并且已经为特殊类型的数字设计了许多复杂的素数分解算法。

整数也可以在高斯素数上进行分解。例如，下表给出了前几个正整数的高斯整数分解。

	分解
1	1
2
3	3
4
5
6
7	7
8
9
10

有趣的是，等于 1 (mod 4) 的素数 总是可以分解为以下形式的高斯素数

其中实部和虚部在两部分中互换，而等于 3 (mod 4) 的素数不能分解为高斯素数。这与费马平方和定理直接相关。