Kennt sich jemand mit dem Sieb des Eratosthenes aus?

...komplette Frage anzeigen

2 Antworten

Sei n die zu prüfende Zahl.

Angenommen, du hast alle Primzahlen bis zur Wurzel von n durchgeprüft und keinen Teiler gefunden. Jetzt prüfst du weiter.

Wenn du jetzt eine Primzahl p > Wurzel(n) findest, dann kannst du n darstellen als:

n = p * r, wobei r das Ergebnis der Division von n durch p ist. Insbesondere ist also r ein Teiler von n.

Da p größer ist als Wurzel n, ist r kleiner als Wurzel n - sonst wäre das Produkt aus beiden ja größer als n, enthält also auch einen Primteiler kleiner als Wurzel n -> den hätten wir aber aber schon gefunden -> Widerspruch.

Das Suchen von großen Primzahlen dauert selbst für schnelle Computer sehr lange! Man versucht daher schon recht früh eine Bedingung zu finden, wo man vorzeitig abbricht,weil es "keine Primzahl" mehr sein kann.

  1. nach der 2 nur noch ungerade Teiler -> also n0=3; n=n+2
  2. nur bis zur Wurzel, da Zahl = Wurzel(Zahl) * Wurzel(Zahl) -> wenn bis zur Wurzel kein Teiler gefunden wurde, dann gibt es keine Möglichkeit, die Zahl als ein Produkt anderer Zahlen > 2 darzustellen

  3. weitere Optimierungen...

Was möchtest Du wissen?