| Autor |
Beitrag |
    
chris
| | Veröffentlicht am Mittwoch, den 04. Oktober, 2000 - 18:27: | 
|
wie bekomme ich ohne primzahltafel leicht heraus ob eine zahl eine primzahl ist oder nich??(die zahl is über 900....) WARUM??? |
Matroid (Matroid)
| | Veröffentlicht am Donnerstag, den 05. Oktober, 2000 - 21:56: |
|
Hallo Chris,
eine Primzahl ist nur durch 1 und sich selbst teilbar (und die kleinste Primzahl ist die 2).
Eine Zahl ist also keine Primzahl, wenn es Zahlen p und q gibt, mit x = p * q. Eine von den beiden Zahlen p und q ist die kleiner von den beiden. Sagen wir mal, die kleinere ist p.
Wenn x keine Primzahl ist, dann können p und q sogar so wählen, daß p der kleinste Primfaktor ist, der x teilt.
Wie groß ist diese kleiner Zahl höchstens? Höchstens Wurzel(x), denn wenn es
einen Zahl r größer als Wurzel(x) gäbe, die ein Teiler von x ist, und die der kleinere der beiden Teiler wäre, dann wäre r also größer als Wurzel x (selbstredend) und r * wurzel(x) > x, aber dann ist r nicht der kleinere der beiden Teiler. Ein Widerspruch.
Was hat man davon? Wenn eine Zahl auf Primzahleigenschaft untersucht werden soll, dann genügt es alle natürlichen Zahlen <= Wurzel(x) zu prüfen, ob sie die Zahl x teilen. Wenn davon keine ein Teiler von x ist, dann ist x eine Primzahl.
Und man muß auch nicht alle Zahlen kleiner Wurzel(x) als möglichen Teiler untersuchen, es reicht natürlich die Primzahlen darunter zu nehmen. Ansonsten gäbe es ja durch anderes Zusammenfassen von Primfaktoren eine andere Möglichkeit für x = p*q, mit einem noch kleineren p - und es war ja angenommen, daß p der kleinste Wert sein sollte.
Nun ein Beispiel:
x= 989. Wurzel(x) = 31,44...
Primzahlen <= 31 sind:
2,3,5,7,11,13,17,19,23,29,31
Man kann nun alles rechnen. Man kann aber auch erst noch ein paar offensichtliche Nicht-Teiler streichen: die 2 und die 3 und die 5.
Wenn einer der Quotienten ganzzahlig ist, dann ist 989 eben keine Primzahl.
Nun 989/7 ist nicht ganzzahlig.
Und 989 durch 11, 13, 17, 19 auch nicht.
Aber 989 / 23 = 43.
Ergebnis 989 ist keine Primzahl.
Und schließlich noch: Man muß eigentlich auch nicht Wurzel(x) berechnen. Vielleicht hat man ja keinen Taschenrechner zur Hand und muß sich auf schriftliches Teilen verlegen.
Dann teilt man eben der Reihe nach die Zahl x durch 7, 11, 13, ....
Und wenn der Quotient anfängt kleiner zu werden als die Zahl, durch die man teilt, dann ist man über Wurzel(x) hinaus und man darf aufhören.
Weiteres Beispiel:
x=907
Primfaktoren 2, 3 und 5 fallen quasi von selbst weg.
907 : 7 = 129,5...
907 : 11 = 82,4...
907 : 13 = 69,7...
907 : 17 = 53,3...
907 : 19 = 47,7...
907 : 23 = 39,4...
907 : 29 = 31,2...
907 : 31 = 29,2...
UND STOP, denn 29,2 ist kleiner als 31, wir sind also über Wurzel(x) hinaus.
Ich würde gern wissen, ob meine Erklärung gut ist. Also ob sie hilft und ob es ein anderes - einfacheres Verfahren - gibt (bei dem man weniger rechnen muß).
Viele Grüße
Matroid |
|
