FANDOM

Gib deine Frage ein...

DefinitionenBearbeiten

40px-Wikipedialogo.png
Wikipediaartikel:
„Primlänge“
40px-Wikipedialogo.png
Wikipediaartikel:
„Primfaktor“
40px-Wikipedialogo.png
Wikipediaartikel:
„Primzahl“

Gegeben sei:

  1. dass die Primlänge die Anzahl der Primfaktoren einer Zahl darstellt.
  2. dass ein Primfaktor eine Primzahl ist, die als Faktor bei der Berechnung des Produkts auftritt, dessen Ergebnis eine Zahl ist. Z.B. wären 2 und 3 Primfaktoren der Zahl 6.
  3. dass eine Primzahl eine natürliche Zahl ist, die genau zwei voneinander verschiedene natürlichen Zahlen als Teiler besitzt, nämlich die Zahl 1 und sich selbst.





PrimzahlenBearbeiten

Diesen Definitionen zufolge hat JEDE Primzahl ungeachtet ihrer Ziffernanzahl eine maximale Primlänge von 1 (um exakt zu sein, eine Primlänge von genau 1), nämlich sich selbst (da 1 per definitionem keine Primzahl ist!).


Natürliche Zahlen außer PrimzahlenBearbeiten

Jede natürliche Zahl in einem Zahlenbereich, deren Primfaktoren sich nicht voneinander unterscheiden müssen, hat eine maximale Primlänge, deren Größe dem Exponent zur Basis 2 entspricht, der die größte Zahl ergibt, die sich von der der größten im Bereich enthaltenen Zahl subtrahieren lässt ohne dass die Differenz negativ wird. Also die höchste Potenz zur Basis 2, deren Ergebnis im Zahlenbereich liegt.


Wenn im gesuchten Zahlenbereich keine Zweierpotenz enthalten ist, so ermittelt man die höchste Zweierpotenz, die unter dem gesuchten Zahlenbereich liegt und verringert diese um 1. Dann wird geprüft, ob sich das Ergebnis dieser Potenz multpliziert mit 3 (drei) im gesuchten Zahlenbereich befindet. Ist dies der Fall, so ist die maximale Primlänge dieselbe wie oben beschrieben (nur ist der letzte Faktor halt eine 3 statt einer 2).


Allgemeiner: Die maximale Primlänge für Zahlen in einem beliebigen Bereich natürlicher Zahlen erhält man wie folgt:

  1. Ermittle den höchsten Exponenten einer Zweierpotenz, deren Ergebnis nicht den Zahlenbereich übersteigt.
  2. Wenn die ermittelte Zweierpotenz Element des zu untersuchenden Zahlenbereiches ist, ist die maximale Primlänge gleich dem ermittelten Exponenten.
  3. Wenn die ermittelte Potenz nicht Element des zu untersuchenden Bereiches ist, wird folgendes Verfahren so lange angewendet, bis das Ergebnis eine Zahl aus dem zu untersuchenden Bereich ist:
    1. Der oben ermittelte Exponent wird um 1 verringert.
    2. Als letzter Faktor wird nun die nächsthöhere Primzahl verwendet, wobei diese nicht höher sein darf als 2^(Gesamtverringerung + 1) und nicht geringer als 2^(Gesamtverringerung). Begründung: Es wurde ja bereits festgestellt, dass Zahlen, die höher sind als die größte ermittelte Zweierpotenz, nicht mehr im zu untersuchenden Bereich liegen ( => x^a * x^b = x^(a + b)). Wenn der Faktor zu gering ist, wird der zu untersuchende Zahlenbereich nicht erreicht werden.
    3. Der letzte Punkt wird so lange wiederholt, bis das Ergebnis den zu untersuchenden Zahlenbereich übersteigt.
    4. Wenn nun immer noch kein Ergebnis vorliegt, wird die Prozedur wiederholt.

Beispiele:

  1. Die maximale Primlänge von Zahlen zwischen 100 und 999 (dreistellige Zahlen)
    1. Die höchste Zweierpotenz lautet 2^9 = 512.
    2. 512 ist Element des zu untersuchenden Zahlenbereiches und somit 9 die maximale Primlänge.
  2. Die maximale Primlänge von Zahlen zwischen 300 und 400
    1. Die höchste Zweierpotenz lautet 2^8 = 256.
    2. 256 ist nicht Element des zu untersuchenden Zahlenbereiches.
    3. Der maximale Exponent wird um 1 verringert: 8 - 1 = 7.
    4. Die nächsthöhere Primzahl wird als Faktor eingesetzt: alter Faktor = 2, neuer Faktor = 3. Das Ergebnis lautet 2^7 * 3 = 128 * 3 = 384.
    5. 384 ist Element des zu untersuchenden Zahlenbereiches und somit 8 die maximale Primlänge.
  3. Die maximale Primlänge von Zahlen zwischen 600 und 700
    1. Die höchste Zweierpotenz lautet 2^9 = 512.
    2. 512 ist nicht Element des zu untersuchenden Zahlenbereiches.
    3. Der maximale Exponent wird um 1 verringert: 9 - 1 = 8.
    4. Die nächsthöhere Primzahl wird als Faktor eingesetzt: alter Faktor = 2, neuer Faktor = 3. Das Ergebnis lautet 2^8 * 3 = 256 * 3 = 768.
    5. 768 ist nicht Element des zu untersuchenden Zahlenbereiches und liegt über derr Obergrenze.
    6. Da 768 bereits das Maximum des zu untersuchenden Zahlenbereiches übershreitet, muss der Faktor nicht weiter erhöht werden und die Schleife geht wieder am Anfang los.
    7. Der maximale Exponent wird um 1 verringert: 8 - 1 = 7.
    8. Die nächsthöhere Primzahl wird als Faktor eingesetzt: alter Faktor = 2, neuer Faktor = 3. Das Ergebnis braucht nicht berechnet zu werden, da der neue Faktor kleiner ist als 2^(Gesamtverringerung) = 2^2 = 4.
    9. Die nächsthöhere Primzahl wird als Faktor eingesetzt: alter Faktor = 3, neuer Faktor = 5. Das Ergebnis lautet 2^7 * 5 = 128 * 5 = 640.
    10. 640 ist Element des zu untersuchenden Zahlenbereichs und somit 8 die maximale Primlänge (nicht 9, wie man vielleicht erwartet hätte)