Primzahl

[implementation]

Eine andere Lösungsidee:

Man nehme ein Array of Boolean und befüllt es mit true.
Jetzt fängt man mit der 2 an (x := 2).
Und geht zunächst jedes zweite Feld durch und setzt es auf false.
Dann stehen arr[4], arr[6] usw. alle auf false.

Nun macht man mit der 3 weiter und schaut sich arr[3] an.
arr[3] ist true, also ist 3 eine Primzahl.
Nun geht man von hier aus wieder jedes dritte Feld durch und setzt es auf false.
Dann stehen arr[9], arr[15] und arr[21] ebenfalls auf false.

Nun die 4: arr[4] ist false -> keine Primzahl!

Weiter zur 5: arr[5] ist true -> Primzahl.
Wieder jedes fünfte Feld auf false setzen: Das wars dann wohl für arr[25] und arr[35].

Weiter zur 6: arr[6] ist false -> keine Primzahl!

Und immer so weiter.