Primzahltest und Sieb

Primzahlen und Primzahltests · Abschnitt 26 von 64

Satz

Die Quadratwurzelgrenze

Ist $n>1$ zusammengesetzt, so besitzt $n$ einen Primteiler $p\le\sqrt n$ . Denn in einer Zerlegung $n=ab$ können nicht beide Faktoren größer als $\sqrt n$ sein.

Gelöstes Beispiel

Vollständiger Test für 97

Weil $\sqrt{97}<10$ , genügen die Primzahlen 2, 3, 5 und 7. Keine davon teilt 97, also ist 97 prim.

Checkliste

Einzelne Zahl testen

Quadratwurzel abschätzen.
Nur Primzahlen bis zu dieser Grenze notieren.
Teilbarkeit durch jede dieser Primzahlen prüfen.
Erst danach „prim“ schließen.

Strategie

Viele Zahlen: das Sieb des Eratosthenes

Schreibe alle Zahlen ab 2 auf. Markiere 2 und streiche ihre echten Vielfachen; wiederhole dies mit der nächsten ungestrichenen Zahl. Für eine Grenze $N$ genügen Streichzahlen bis $\sqrt N$ .