Primzahl - Möglichkeiten um eine Zahl zu überprüfen (Nur bis wurzel(x))?
Hi,
ich habe mir grade ein C++ Code angeschaut womit man Zahlen ueberpruefen kann ob sie eine Primzahl sind oder nicht.
Der Code funktioniert...
Wenn die Zahl n zu überprüfen ist, prüft der code ob die Zahlen in den Grenzen von 2 bis wurzel(n) durch eine andere Teilbar ist. Wenn ja => Keine Primzahl, wenn nicht => Primzahl.
Meine Frage ist, warum reicht es aus wenn man die Grenzen von 2 bis wurzel(n) überprüft. Warum muss man nicht 2 bis n überprüfen?
Lg
6 Antworten
Nehmen wir als Beispiel die Zahl 100. Wir fangen an die Teiler zu testen. 2 ist ein Teiler, weil 2*50 = 100. Ah, also ist 50 auch ein Teiler. Gut, klar. Es gibt immer ein Gegenstück zum kleinen Teiler 2, den Teiler 50. Weiter gehts. 4*25 = 100. Gleiches Prinzip.
Die Wurzel von 100 ist 10. 10*10 ist gleich 100. Das bedeutet, wenn man nun einen Teiler hätte der größer ist als 10, dann hätte der ein Gegenstück was kleiner ist als 10. Nach der 20 z.B. müssten wir nicht suchen, denn wenn die 20 ein Teiler ist von 100, dann haben wir bereits das Gegenstück...die 5...gefunden, als wir bis WURZEL(100) getestet haben.
Ich hoffe, das ergibt so Sinn. Außerdem musst du auch nur die Primzahlen bis WURZEL(n) testen, das hat mit der Primfaktorzerlegung zu tun.
Ganz einfach, wenn die Zahl p keine Primzahl ist, dann gibt es zwei Zahlen a und b ( ungleich 1) so das a*b = p ist. Wenn jezt sowohl a als auch b > wurzel(p) sind, dann ist ihr Produkt > wurzel(p)*wurzel(p) also größer als p und kann somit nicht gleich p sein. Insweit muß es bei einer nicht Primzahl einen Teiler geben, der kleiner ist als die Wurzel der Zahl.
Warum das geht, wurde bereits erklärt, eine weitere Verbesserung des Algorithmus ergibt sich, wenn die Teilbarkeit durch 2 vorweg ausgeschlossen wird, dann genügt es, die Teilbarkeit durch die ungeraden Zahlen ab drei zu prüfen.
Und auch nur durch die kleineren Primzahlen;
die muss man sich dann aber merken.
Wenn du größere Zahlen überprüfst, kommen als
Ergebnis wieder kleinere raus, die hast du aber schon
überprüft, also du "von unten" angefangen hast.
Beispiel: 19, zu überprüfen bis 4.
19 / 2 = 9 R. 1
19 / 3 = 6 R. 1
19 / 4 = 4 R. 3
19 / 5 = 3 R. 4
(merkst du was? die 3 war schon dran)
Und natürlich musst du außer 2 nur
ungerade Zahlen testen. Übrigens auch
nur Primzahlen, aber das ist eine
andere Baustelle.
1. Sei a die Wurzel von n (a nicht unbedingt ganzzahlig), dann ist a * a = n; klar
2. Sei n keine Primzahl, d.h. es gibt zwei ganze Zahlen b und c mit: b * c = n
3. Wenn beide Zahlen b und c > a wären, dann muß b * c > a * a und somit ungleich n
4. Also muß mindestens eine der beiden (b,c) kleiner als a sein. (es ist tatsächlich immer nur eine kleiner ...)
5. Um rauszufinden, daß n keine Primzahl ist, muß Du nur nach der kleineren des Paares b,c suchen und erhältst die andere automatisch.
6. Deshalb kann deine Routine bei a aufhören.