Fastprimzahl
# Fastprimzahl

Eine $n$-Fastprimzahl oder auch Fastprimzahl $n$-ter Ordnung ist eine natürliche Zahl, deren Primfaktorzerlegung aus genau $n$ Primzahlen besteht, wobei mehrfache Primteiler entsprechend oft gezählt werden. Da alle natürlichen Zahlen größer eins aus Primfaktoren zusammengesetzt sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung (also die Produkte von genau zwei Primzahlen) nennt man auch Semiprimzahlen.
Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren hochzusammengesetzten Zahlen und schließen dabei beide mit ein.
Der Norweger Viggo Brun führte den Begriff um 1915 zur Verallgemeinerung von Primzahlen ein, um einen neuen Ansatz für ungelöste Primzahlprobleme zu finden.

## Definition

Sei $z\in \mathbb {N} \setminus \{0\}$ und $\textstyle z=\prod _{i=1}^{k}{p_{i}}^{e_{i}}$ mit Primzahlen $p_{1},\dotsc ,p_{k}$. Dann heißt $z$ Fastprimzahl $n$-ter Ordnung, wobei $\textstyle n=\sum _{i=1}^{k}e_{i}$ gilt. Die Zahlenfolge für ein festes $n$ wird auch mit $P_{n}$ bezeichnet. Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung für alle natürlichen Zahlen.
Dieses Konzept kann problemlos auf die ganzen Zahlen und beliebige ZPE-Ringe verallgemeinert werden.

## Beispiele und Werte

Beispiele:
* $13$ ist eine Fastprimzahl erster Ordnung („Primzahl“).
* $91=7\cdot 13$ ist eine Fastprimzahl zweiter Ordnung („Semiprimzahl“).
* $100=2^{2}\cdot 5^{2}$ ist eine Fastprimzahl vierter Ordnung.
* $1024=2^{10}$ ist eine Fastprimzahl zehnter Ordnung.
* $5308416=2^{16}\cdot 3^{4}$ ist eine Fastprimzahl zwanzigster Ordnung.
Die ersten zwölf Fastprimzahlen erster bis zwanzigster Ordnung :
| 01. Ordnung | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | … | Folge A000040 in OEIS |
| 02. Ordnung | 4 | 6 | 9 | 10 | 14 | 15 | 21 | 22 | 25 | 26 | 33 | 34 | … | Folge A001358 in OEIS |
| 03. Ordnung | 8 | 12 | 18 | 20 | 27 | 28 | 30 | 42 | 44 | 45 | 50 | 52 | … | Folge A014612 in OEIS |
| 04. Ordnung | 16 | 24 | 36 | 40 | 54 | 56 | 60 | 81 | 84 | 88 | 90 | 100 | … | Folge A014613 in OEIS |
| 05. Ordnung | 32 | 48 | 72 | 80 | 108 | 112 | 120 | 162 | 168 | 176 | 180 | 200 | … | Folge A014614 in OEIS |
| 06. Ordnung | 64 | 96 | 144 | 160 | 216 | 224 | 240 | 324 | 336 | 352 | 360 | 400 | … | Folge A046306 in OEIS |
| 07. Ordnung | 128 | 192 | 288 | 320 | 432 | 448 | 480 | 648 | 672 | 704 | 720 | 800 | … | Folge A046308 in OEIS |
| 08. Ordnung | 256 | 384 | 576 | 640 | 864 | 896 | 960 | 1296 | 1344 | 1408 | 1440 | 1600 | … | Folge A046310 in OEIS |
| 09. Ordnung | 512 | 768 | 1152 | 1280 | 1728 | 1792 | 1920 | 2592 | 2688 | 2816 | 2880 | 3200 | … | Folge A046312 in OEIS |
| 10. Ordnung | 1024 | 1536 | 2304 | 2560 | 3456 | 3584 | 3840 | 5184 | 5376 | 5632 | 5760 | 6400 | … | Folge A046314 in OEIS |
| 11. Ordnung | 2048 | 3072 | 4608 | 5120 | 6912 | 7168 | 7680 | 10368 | 10752 | 11264 | 11520 | 12800 | … | Folge A069272 in OEIS |
| 12. Ordnung | 4096 | 6144 | 9216 | 10240 | 13824 | 14336 | 15360 | 20736 | 21504 | 22528 | 23040 | 25600 | … | Folge A069273 in OEIS |
| 13. Ordnung | 8192 | 12288 | 18432 | 20480 | 27648 | 28672 | 30720 | 41472 | 43008 | 45056 | 46080 | 51200 | … | Folge A069274 in OEIS |
| 14. Ordnung | 16384 | 24576 | 36864 | 40960 | 55296 | 57344 | 61440 | 82944 | 86016 | 90112 | 92160 | 102400 | … | Folge A069275 in OEIS |
| 15. Ordnung | 32768 | 49152 | 73728 | 81920 | 110592 | 114688 | 122880 | 165888 | 172032 | 180224 | 184320 | 204800 | … | Folge A069276 in OEIS |
| 16. Ordnung | 65536 | 98304 | 147456 | 163840 | 221184 | 229376 | 245760 | 331776 | 344064 | 360448 | 368640 | 409600 | … | Folge A069277 in OEIS |
| 17. Ordnung | 131072 | 196608 | 294912 | 327680 | 442368 | 458752 | 491520 | 663552 | 688128 | 720896 | 737280 | 819200 | … | Folge A069278 in OEIS |
| 18. Ordnung | 262144 | 393216 | 589824 | 655360 | 884736 | 917504 | 983040 | 1327104 | 1376256 | 1441792 | 1474560 | 1638400 | … | Folge A069279 in OEIS |
| 19. Ordnung | 524288 | 786432 | 1179648 | 1310720 | 1769472 | 1835008 | 1966080 | 2654208 | 2752512 | 2883584 | 2949120 | 3276800 | … | Folge A069280 in OEIS |
| 20. Ordnung | 1048576 | 1572864 | 2359296 | 2621440 | 3538944 | 3670016 | 3932160 | 5308416 | 5505024 | 5767168 | 5898240 | 6553600 | … | Folge A069281 in OEIS |

## Eigenschaften

* Jede Primzahl ist eine Fastprimzahl der Ordnung 1, jede zusammengesetzte Zahl ist eine Fastprimzahl der Ordnung 2 oder höher. Fastprimzahlen dritter Ordnung, sofern diese aus 3 verschiedenen Primfaktoren bestehen, nennt man auch sphenische Zahlen.
* Die Vereinigung der $P_{n}$ bilden eine Zerlegung der natürlichen Zahlen.
* Jede Fastprimzahl $n$-ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen $k_{1},\dotsc ,k_{m}$ mit $\sum _{i=1}^{m}k_{i}=n$, z. B.: Das Produkt der 3-Fastprimzahl 12 und der 4-Fastprimzahl 40 ergibt die 7-Fastprimzahl 480. Für $k_{1},\dotsc ,k_{m}>0$ gibt es $S_{n,m}$ solcher möglichen Zerlegungen, wobei $S_{n,m}$ die Stirling-Zahlen zweiter Art bezeichnet.
* Da es für die Null keine mögliche Primfaktorzerlegung gibt, ist sie keine Fastprimzahl $n$-ter Ordnung.
* Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
* Sei $\pi _{k}(n)$ die Anzahl der positiven ganzen Zahlen kleiner gleich $n$ mit genau $k$ Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt: $\pi _{k}(n)\sim {\frac {n}{\log n}}\cdot {\frac {(\log \log n)^{k-1}}{(k-1)!}}$
* Jede genügend große gerade Zahl lässt sich als die Summe zweier Primzahlen oder einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen. Diese Aussage hat Ähnlichkeit mit der Goldbachschen Vermutung, wurde 1978 von Chen Jingrun bewiesen und nennt sich Satz von Chen.
* Es gibt unendlich viele Primzahlen, sodass $p+2$ eine 2-Fastprimzahl ist. Diese Aussage hat Ähnlichkeit mit der Vermutung über Primzahlzwillinge und wurde ebenfalls von Chen bewiesen.

## Anwendungen

Fastprimzahlen zweiter Ordnung, also Produkte zweier Primzahlen, finden in der Kryptographie Anwendung.