Primzahl

Um in einem begrenzten Bereich die Primzahlen zu berechnen, eignet sich das Sieb des Eratosthenes sehr gut. Insbesondere dann, wenn es optimiert ist.

Man erzeugt ein Feld von Zahlen angefangen von 2 bis zu einer wilkürlich gewählten höchsten Zahl (sagen wir mal 10.000, das ist das Quadrat von 100). 2 ist die erste Zahl in dem Feld, und demnach ist 2 eine Primzahl, und wird demnach als solche markiert oder auch freigelassen. Nun werden von 4 (2 zum Quadrat) an jede 2 Zahl durchgestrichen. Also 4, 6, 8, bis 10.000. Nun wird die nächste nicht angestrichene Zahl (3) markiert, und von 9 an jede 3. Zahl angestrichen. das Ganze macht man bis zur 97 (letzte Primzahl vor der Hundert). Alle jetzt noch nicht angestrichenen Zahlen sin automatisch Primzahlen.