# Ablaufdiagramm: Primzahlberechnung



## dschises (5. Sep 2009)

Servus,
hab mir diese Ablaufdiagramm angesehen und auch fast alles verstanden, 
nur die Abfrage i*i > n hat mich stutzig werden lassen.
Stände da i >= n/2 wäre alles klar, aber wiso kann ich schon aufhören die teiler zu überprüfen wenn deren quadrat größer ist als die zu überprüfende Zahl







Wenn mir das jemand erklären könnte wäre ich sehr froh


----------



## bygones (5. Sep 2009)

n/2 stimmt so und so nicht... wenn dann die wurzel von n
ob man bei einem das quadrat nimmt oder beim anderen die wurzel ist das selbe...


----------



## dschises (5. Sep 2009)

sry ich hab dich nicht verstanden...


----------



## tfa (5. Sep 2009)

Der kleinste Teiler einer Nicht-Primzahl kann höchstens so groß sein wie die Quadratwurzel dieser Zahl.


----------



## dschises (6. Sep 2009)

ok habs verstanden danke


----------

