Wie weiss man, dass das eine Primzahl ist? :O
Gueten Abend,
Ich habe morgen einen Test über Primzahlen. Wie kann ich herausfinden, dass das eine Primzahl ist und dass das keine ist?
9 Antworten
Eine Primzahl lässt sich nur durch sich selbst und durch 1 teilen, wobei zubeachten ist, dass der Quotient eine ganze Zahl sein muss.
Bsp.: 8 ist keine Primzahl, denn sie lässt sich restlos durch 1,2,4 und 8 teilen. 7 ist eine Primzahl, da sie sich restlos nur durch 1 und sich selbst (also 7) teilen.
MfG
Wenn sie eine pimzahl ist lässt sie sich nur durch sich selber teilen und durch 1
Bei wirklich großen Zahlen lässt sich das nicht so einfach sicher herausfinden.
Es gibt statistische Tests, beispielsweise den "Miller-Rabin-Test". Dadurch kannst Du mit einer (möglichst hohen) Wahrscheinlichkeit feststellen, ob eine Zahl eine Primzahl ist. Solche Tests kommen beispielsweise in der Kryptographie zum Einsatz, wo man häufig sehr große Primzahlen mit mehreren hundert Dezimalstellen benötigt.
Wenn Du es genau wissen willst (also nicht nur statistisch), musst Du tatsächlich durch alle Zahlen bis zur Wurzel der Zahl, die Du testen möchtest, teilen, und überprüfen, ob sich ein Divisionsrest ergibt.
Wobei man dann die Zahlen unterhalb der Wurzel widerum darauf prüfen muss, ob sie prim sind, womit wir (fast) wieder beim ursprünglichen Problem wären. Kann man natürlich "rekursiv definieren", wird allerdings erheblich länger dauern, als einfach mit allen Zahlen zu testen, weil es erheblich aufwändiger ist, zu prüfen, ob eine Zahl prim ist (denn das braucht ja allein schon viele "Probedivisionen", also Modulo-Operationen), als zu prüfen, ob diese Zahl die zu testende Zahl teilt (das braucht nur eine Modulo-Operation).
Eine Primzahl hat immer genau zwei Teiler - die eins und sich selbst.
Somit ist 1 keine Primzahl, weil sie nur einen Teiler hat. 2,3,5,7,11 ... sind z.B. Primzahlen. Mit dem Sieb des Eratosthenes kann man leicht die Primzahlen bis 100 bestimmen. Das lässt sich leicht googlen. Du muss Dich bei jeder Zahl fragen, ob man sie noch durch eine andere Zahl als 1 und sich selbst teilen kann.
Bei großen Zahlen solltest Du die Teilbarkeitsregeln durchgehen. Damit findet man nicht unbedingt alle, aber die meisten.
Das müsst Ihr doch geübt haben?
Ob eine Zahl durch 2, 5 und deren Vielfache teilbar ist, sieht man auf dem ersten Blick. Für die Prüfung auf 3 und deren Vielfache braucht man die Quersumme, das geht auch schnell. Aber 7, 11, 13, 17, . . . ?
Bei 11 kann man immerhin noch entweder die "alternierende Quersumme" nehmen, also die Ziffern abwechselnd addieren und subtrahieren - die Ausgangszahl ist durch 11 teilbar genau dann wenn dies auch für diese Summe gilt, oder man rechnet im 100er-System, am einfachsten, indem man jeweils 2 Ziffern im Zehnersystem zusammenfasst (von rechts angefangen) - dann ist eine Zahl genau dann durch 11 teilbar, wenn dies auch für diese Quersumme gilt.
Allerdings braucht man nicht mehr die Zahlen a * n zu testen, wenn man a als Teiler bereits ausgeschlossen hat.
Somit braucht man eigentlich nur die Zahl 2 und sämtliche Primzahlen ab 3 bis zur Wurzel der zu prüfenden Zah zu testen..