Ich habe mal gelesen, das es reicht, bis zur Wurzel der Zahl zu überprüfen, nicht bis zur Hälfte.