Verfahren, mit denen man Primzahltests durchführen kann?

... komplette Frage anzeigen

6 Antworten

Eine Primzahl ist eine Zahl die nur durch 1 und durch sich selbst teilbar ist.

Das einfachste und primitivste Verfahren lässt einfach eine Zählschleife von 1 bis n (deine Zahl) laufen und schaut ob deine Zahl ohne Rest teilbar ist oder nicht, ist deine Zahl durch keine Zahl ohne Rest teilbar außer durch 1 und sich selbst, dann ist es eine Primzahl.

Bessere Verfahren findest du in Büchern zur numerischen Mathematik.

Hier kannst du auch mal schauen --> http://primzahlen.zeta24.com/

Antwort bewerten Vielen Dank für Deine Bewertung

Es gibt mehrere Ansätze, um Primzahlen zu ermitteln.

Wenn du einfach nur wissen willst, ob deine Zahl eine Primzahl ist, hier ein Online-Checker: http://www.arndt-bruenner.de/mathe/scripts/primzahlen.htm

Wenn du selbst Hand anlegen willst, kannst du den Miller-Rabin Tests verwenden, der nach wenigen "Runden" mit einer Wahrscheinlichkeit von unter einem Billiardstel feststellt, ob deine Zahl eine Primzahl ist.

Antwort bewerten Vielen Dank für Deine Bewertung

Bei dieser Aufgabe (aktueller BW Math) musst du anders ansetzen, zumal Computer als Hilfsmittel nicht erlaubt sind.

Wenn du die Zahl mit 99 malnimmst, erhältst du eine Zahl aus 4035 Neunen, das ist 10^4036-1 bzw. (10^2018-1)(10^2018+1). Von diesen beiden Faktoren ist einer durch 9 der andere durch 11 teilbar, so dass die ursprüngliche Zahl (mindestens) aus den Faktoren (10^2018-1)/9 und (10^2018+1)/11 besteht.

Antwort bewerten Vielen Dank für Deine Bewertung

Hallo,

im allgemeinen mußt Du eine Zahl nur durch alle Primzahlen teilen, die kleiner oder gleich der Wurzel der nächstunteren Quadratzahl sind.

Für Zahlen bis 120 reicht es also aus, sie durch 2, 3, 5 und 7 zu teilen, um sie zu testen. Erst ab der 121, 11² kann es vorkommen, daß unter den möglichen Teilern keine Primzahl bis 7 dabei ist und die Zahl dennoch Teiler außer 1 und der Zahl selbst hat. 

Bei Zahlen in dieser gewünschten Größenordnung erleichtert dies zwar die Aufgabe, weil Du Dich nur noch im Zahlenbereich unterhalb der Quadratwurzel der zu testenden Zahl befindest; sie ist aber immer noch viel zu groß, um alle Möglichkeiten durchzuprobieren.

Herzliche Grüße,

Willy

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Hansi412
26.12.2015, 12:58

Ja die Zahl ist echt groß...

1

eine primzahl ist nur durch 1 und sich selbst teilbar. wenn du also k=1234 hast, ist es eine primzahl. wenn k/5 und k/2 und k/3 einen rest ergeben, ist es eine primzahl. es muss gelten k/1=k und k/k=1, aber das trifft ja für ALLE zahlen zu.

sprich du musst die einzelnen zahlen untersuchen, ist bei k/5, k/3 und k/2 die erste nachkommastelle gleich 0, ist es keine primzahl. ist sie ungleich 0 dann ist es eine primzahl.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Hansi412
26.12.2015, 12:40

Danke für deine Antwort, jedoch ist die Zahl (wie erwähnt) so groß, dass ich sie nicht einfach in den Taschenrechner eingeben kann...

0

Eine spontane Möglichkeit die mir einfallen würde ist die Zahl %(modulo) alle anderen Zahlen zu rechnen, also 1,2,3,4,5,6,7,8,9. Wenn %1 = 0 ergibt und 2,3,4,5,6,7,8,9 !=(ungleich) 0 ist die Zahl eine Primzahl.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von claushilbig
27.12.2015, 22:30

Nur bis 9 zu testen, reicht nicht. Bei dem Verfahren musst Du alle Primzahlen bis zur Wurzel der untersuchten Zahl ausprobieren.

Z. B. ist 121 nicht durch 2 bis 9 teilbar, aber keine Primzahl (11x11)

0

Was möchtest Du wissen?