素數分解

將一個數分解成其組成的因子，也稱為素因子分解。給定一個正整數 ，素數分解可以寫成

其中 是 個 素因子，每個素因子的階數為 。每個因子 稱為一個 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) 的素數不能分解為高斯素數。這與費馬平方和定理直接相關。