Primzahl-Test

• Man prüft für alle Primzahlen $\leq\sqrt{x}$, ob sie $x$ teilen $\quad\rightarrow$ ggf. Primzahl-Liste nutzen
  -> Wenn kein Teiler gefunden wird, ist $x$ eine Primzahl

$\quad$

1. Bestimmung von $\sqrt{67} \approx 8,19$
2. Liste der zu prüfende Primzahlen:$\quad 2, 3, 5, 7$
3. Prüfung der Primzahl Liste
   • 67 durch 2 → keine ganze Zahl
   • 67 durch 3 → keine ganze Zahl
   • 67 durch 5 → keine ganze Zahl
   • 67 durch 7 → keine ganze Zahl
     $\quad$
4. Ergebnis:
   Es gibt keine Primzahl kleiner $\sqrt{67}$, die $67$ teilt$\quad\rightarrow\quad 67$ ist eine Primzahl!