Man kann jede natürliche Zahl als ein Produkt aus Primzahlen (bzw. Potenzen von Primzahlen) zerlegen, diese Operation nennt man Primfaktorzerlegung.
Beispiele:
6 = 2 · 3
84 = 2 · 2 · 3 · 7 = 22 · 3 · 7
111 = 3 · 37
2940 = 22 · 3 · 5 · 72
96.320.367.000 = 23 · 33 · 53 · 11 · 132 · 19 · 101
Es gibt, außer Ausprobieren, kein sicheres allgemeines Verfahren für eine Primfaktorzerlegung, und bei großen Zahlen dauert das Ausprobieren unvorstellbar lange.