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