Primfaktorzerlegung

Die Primfaktorzerlegung ist die Darstellung einer positiven natürlichen Zahl ${\displaystyle n\in \mathbb {N} }$ als Produkt aus Primzahlen ${\displaystyle p\in \mathbb {P} ,}$ die dann als Primfaktoren von ${\displaystyle n}$ bezeichnet werden. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine Multimenge) und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie. Sie ist Gegenstand des Fundamentalsatzes der Arithmetik. Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.

Zahl	Faktoren einzeln	Anzahl	Faktoren kanonisch
1	–	0	–
2	${\displaystyle 2}$	1	${\displaystyle 2}$
3	${\displaystyle 3}$	1	${\displaystyle 3}$
4	${\displaystyle 2\cdot 2}$	2	${\displaystyle 2^{2}}$
5	${\displaystyle 5}$	1	${\displaystyle 5}$
6	${\displaystyle 2\cdot 3}$	2	${\displaystyle 2\cdot 3}$
7	${\displaystyle 7}$	1	${\displaystyle 7}$
8	${\displaystyle 2\cdot 2\cdot 2}$	3	${\displaystyle 2^{3}}$
9	${\displaystyle 3\cdot 3}$	2	${\displaystyle 3^{2}}$
10	${\displaystyle 2\cdot 5}$	2	${\displaystyle 2\cdot 5}$
11	${\displaystyle 11}$	1	${\displaystyle 11}$
12	${\displaystyle 2\cdot 2\cdot 3}$	3	${\displaystyle 2^{2}\cdot 3}$
13	${\displaystyle 13}$	1	${\displaystyle 13}$
14	${\displaystyle 2\cdot 7}$	2	${\displaystyle 2\cdot 7}$
15	${\displaystyle 3\cdot 5}$	2	${\displaystyle 3\cdot 5}$
16	${\displaystyle 2\cdot 2\cdot 2\cdot 2}$	4	${\displaystyle 2^{4}}$
17	${\displaystyle 17}$	1	${\displaystyle 17}$
18	${\displaystyle 2\cdot 3\cdot 3}$	3	${\displaystyle 2\cdot 3^{2}}$
19	${\displaystyle 19}$	1	${\displaystyle 19}$
20	${\displaystyle 2\cdot 2\cdot 5}$	3	${\displaystyle 2^{2}\cdot 5}$