imported>Hutch: Leerzeichen vor/nach Schrägstrich korrigiert

2024-07-08T07:25:34Z

Leerzeichen vor/nach Schrägstrich korrigiert

Neue Seite

Eine '''<math>n</math>-Fastprimzahl''' oder auch '''Fastprimzahl <math>n</math>-ter Ordnung''' ist eine [[natürliche Zahl]], deren [[Primfaktorzerlegung]] aus genau <math>n</math> [[Primzahl]]en besteht, wobei mehrfache Primteiler entsprechend oft gezählt werden. Da alle natürlichen Zahlen größer eins aus Primfaktoren [[Zusammengesetzte Zahl|zusammengesetzt]] sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung (also die [[Produkt (Mathematik)|Produkte]] von genau zwei Primzahlen) nennt man auch '''Semiprimzahlen.'''

Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren [[Hochzusammengesetzte Zahl|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.<ref>Wolfgang Blum: ''Goldbach und die Zwillinge.'' In: ''[[Spektrum der Wissenschaft]]'', Dezember 2008, S. 97 (reproduziert: [https://www.spiegel.de/wissenschaft/mensch/primzahlen-wer-lueftet-das-geheimnis-der-unteilbarkeit-a-598096.html ''Primzahlen: Wer lüftet das Geheimnis der Unteilbarkeit?''] [[Spiegel Online]], 25. Dezember 2008; abgerufen am 24. August 2018).</ref>

== Definition ==
Sei <math>z \in \mathbb N \setminus \{0\}</math> und <math>\textstyle z = \prod_{i=1}^k{p_i}^{e_i}</math> mit Primzahlen <math>p_1, \dotsc, p_k</math>. Dann heißt <math>z</math> Fastprimzahl <math>n</math>-ter Ordnung, wobei <math>\textstyle n=\sum_{i=1}^ke_i</math> gilt. Die Zahlen[[Folge (Mathematik)|folge]] für ein festes <math>n</math> wird auch mit <math>P_n</math> bezeichnet.<ref>Paulo Ribenboim: ''Die Welt der Primzahlen. Geheimnisse und Rekorde.'' Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219.</ref> Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung für alle natürlichen Zahlen.

Dieses Konzept kann problemlos auf die [[Ganze Zahl|ganzen Zahlen]] und beliebige [[ZPE-Ring]]e verallgemeinert werden.

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

== 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 Zahl|sphenische Zahlen]].
* Die Vereinigung der <math>P_n</math> bilden eine [[Partition (Mengenlehre)|Zerlegung]] der natürlichen Zahlen.
* Jede Fastprimzahl <math>n</math>-ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen <math>k_1, \dotsc, k_m</math> mit <math>\sum_{i=1}^mk_i=n</math>, z. B.: Das Produkt der 3-Fastprimzahl 12 und der 4-Fastprimzahl 40 ergibt die 7-Fastprimzahl 480. Für <math>k_1, \dotsc, k_m > 0</math> gibt es <math>S_{n,m}</math> solcher möglichen Zerlegungen, wobei <math>S_{n,m}</math> die [[Stirling-Zahl]]en zweiter Art bezeichnet.
* Da es für die [[Null]] keine mögliche Primfaktorzerlegung gibt, ist sie ''keine'' Fastprimzahl <math>n</math>-ter Ordnung.
* Der [[Eins]] wird das [[Leeres Produkt|leere Produkt]] als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
* Sei <math>\pi_k(n)</math> die Anzahl der positiven ganzen Zahlen kleiner gleich <math>n</math> mit genau <math>k</math> Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt:<ref>{{Internetquelle |autor=[[Edmund Landau]] |url=https://archive.org/details/handbuchderlehre01landuoft |titel=Handbuch der Lehre von der Verteilung der Primzahlen |hrsg=B. G. Teubner |seiten=211 |datum=1909 |abruf=2018-06-30}}</ref><br /> <math>\pi_k(n) \sim \frac{n}{\log n} \cdot \frac{(\log \log n)^{k-1}}{(k-1)!}</math>
* Jede genügend große gerade Zahl lässt sich als die Summe zweier Primzahlen oder einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen.<ref name="Chen">{{Internetquelle |autor=Konstantin Fackeldey |url=https://www.researchgate.net/profile/Konstantin_Fackeldey/publication/266442896_Die_Goldbachsche_Vermutung_und_ihre_bisherigen_Losungsversuche/links/573ef91508ae9ace8413360f/Die-Goldbachsche-Vermutung-und-ihre-bisherigen-Loesungsversuche.pdf |titel=Die Goldbachsche Vermutung und ihre bisherigen Lösungsversuche |hrsg=[[Freie Universität Berlin]] |seiten=25–27 |datum=2002 |format=PDF |abruf=2018-06-30}}</ref><br /> Diese Aussage hat Ähnlichkeit mit der [[Goldbachsche Vermutung|Goldbachschen Vermutung]], wurde 1978 von [[Chen Jingrun]] bewiesen und nennt sich [[Satz von Chen]].
* Es gibt unendlich viele Primzahlen, sodass <math>p+2</math> eine 2-Fastprimzahl ist.<ref name="Chen" /><br /> Diese Aussage hat Ähnlichkeit mit der [[Vermutung (Mathematik)|Vermutung]] über [[Primzahlzwilling]]e und wurde ebenfalls von Chen bewiesen.

== Anwendungen ==
Fastprimzahlen zweiter Ordnung, also Produkte zweier Primzahlen, finden in der [[Kryptographie]] Anwendung.

== Weblinks ==
* {{MathWorld |id=AlmostPrime |title=Almost prime}} Fastprimzahlen
* {{MathWorld |id=Semiprime |title=Semiprime}} Fastprimzahlen 2. Ordnung

== Literatur ==
* [[Władysław Narkiewicz]]: ''The Development of Prime Number Theory. From Euclid to Hardy and Littlewood.'' Springer, Berlin u. a. 2000, ISBN 3-540-66289-8.
* [[Hans Riesel]]: ''Prime Numbers and Computer Methods for Factorization.'' Birkhäuser, Boston/Basel/Stuttgart 1985, ISBN 3-7643-3291-3.
* David M. Bressoud: ''Factorization and Primality Testing.'' Springer, New York u. a. 1989, ISBN 0-387-97040-1.
* [[Paulo Ribenboim]]: ''The little book of bigger primes.'' 2. Ausgabe. Springer, New York u. a. 2004, ISBN 0-387-20169-6.
* ''Die Welt der Primzahlen. Geheimnisse und Rekorde.'' Auf den neuesten Stand gebracht von Wilfrid Keller. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0.

== Einzelnachweise ==
<references />

{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]

Fastprimzahl - Versionsgeschichte

imported>Hutch: Leerzeichen vor/nach Schrägstrich korrigiert