Die wohl einfachste und elementarste Lösung ist folgende:
Man suchte eben alle Primzahlen zwischen ]2; n]. Und zwar prüft man die Zahl x, indem man jede Zahl zwischen ]2; x] mit den schon gefundenen Primzahlen prüft (auf eben restlose Teilbarkeit).
Eine schnellere Methode wäre, ein Array mit der Größe n (1 initialisiert) zu erstellen und dann 2 verschachtelte Schleifen die von 2 bis n/2 laufen und jeweils in array[index1*index2]=0 setzen.
Jede Position, an der eine 1 steht, stellt eine Primzahl dar.
Ich hoffe, das reicht,
Stefan!