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