Κόσκινο του Ερατοσθένη

Το Κόσκινο του Ερατοσθένη είναι ένας απλός αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι έναν συγκεκριμένο ακέραιο.

Πρώτος αριθμός (ή απλά πρώτος) είναι ένας φυσικός αριθμός μεγαλύτερος της μονάδας με την ιδιότητα οι μόνοι φυσικοί διαιρέτες του να είναι η μονάδα και ο εαυτός του.

Η εύρεση όλων των πρώτων αριθμών που είναι μικρότεροι ή ίσοι από έναν ακέραιο n, σύμφωνα με τη μέθοδο του Ερατοσθένη, γίνεται ως εξής:

• Δημιουργούμε μια λίστα από διαδοχικούς ακέραιους από το 2 μέχρι το n : (2, 3, 4, ..., n).
• Αρχικά, έστω ότι το p είναι ίσο με 2, τον 1^ο πρώτο (και μοναδικό άρτιο) αριθμό.
• Διαγράφουμε από τη λίστα όλα τα πολλαπλάσια του p που είναι μικρότερα ή ίσα με n. (2p, 3p, 4p, κτλ)
• Βρίσκουμε τον 1^ο αριθμό που απομένει στη λίστα μετά τον p (αυτός ο αριθμός είναι ο επόμενος πρώτος αριθμός) και αντικαθιστούμε το p με αυτόν τον αριθμό.
• Επαναλαμβάνουμε τα βήματα 3 και 4 μέχρι το p² να είναι μεγαλύτερο από n.
• Όλοι οι αριθμοί που απομένουν στη λίστα είναι πρώτοι αριθμοί.