Στα μαθηματικά, το Κόσκινο του Ερατοσθένη είναι ένας απλός αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι έναν συγκεκριμένο ακέραιο. Σαν αλγόριθμος είναι γρήγορος για μικρούς πρώτους (κάτω από 10 εκατομμύρια). Δημιουργήθηκε από τον Ερατοσθένη, μαθηματικό της Αρχαίας Ελλάδας.

Σύμφωνα με τον αλγόριθμο αυτό ακολουθούμε τα επόμενα βήματα:

• Γράφουμε διαδοχικά τους ακέραιους αριθμούς από το 2 ως τον μεγαλύτερο αριθμό ν που επιθυμούμε να συμπεριλάβουμε στον πίνακα. Το 1 δεν είναι ούτε πρώτος ούτε σύνθετος.
• Διαγράφουμε όλους τους αριθμούς τους μεγαλύτερους από 2 που διαιρούνται με το 2 (δηλαδή κάθε δεύτερο αριθμό).
• Βρίσκουμε τον μικρότερο εναπομείναντα αριθμό μεγαλύτερο του 2, δηλαδή τον 3.   Διαγράφουμε   όλους   τους   αριθμούς   τους μεγαλύτερους από 3 που διαιρούνται με το 3 (δηλαδή κάθε τρίτο αριθμό).
• Βρίσκουμε τον μικρότερο εναπομείναντα αριθμό μεγαλύτερο του 3, δηλαδή τον 5. Διαγράφουμε όλους τους αριθμούς τους μεγαλύτερους από 5 που διαιρούνται με το 5 (δηλαδή κάθε πέμπτο αριθμό).
• Συνεχίζουμε μέχρι να έχουμε διαγράψει όλους τους αριθμούς που διαιρούνται με το ακέραιο μέρος της τετραγωνικής ρίζας του ν. Για παράδειγμα αν ο μεγαλύτερος αριθμός μας είναι ν=120 τότε συνεχίζουμε τη διαδικασία μέχρι που να διαγράψουμε και τα πολλαπλάσια του ακεραίου μέρους της τετραγωνικής ρίζας του 120 που είναι το 10.
• Οι αριθμοί που απομένουν είναι οι πρώτοι αριθμοί από το 1 έως το ν.

Δείτε επίσης το βίντεο   (χρησιμοποιήστε κατάλληλα τα κουμπιά για να περιηγηθείτε σε όλες τις διαφάνειες του).

Επίσης μπορείτε να βρείτε όλους τους πρώτους αριθμούς, που περιέχονται μεταξύ δύο άλλων, στην παρακάτω διαδραστική ιστοσελίδα:  Sieve of Eratosthenes