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

Ερατοσθένης ο Κυρηναίος 276-198 π.Χ.

Το πρόβλημα της εύρεσης πρώτων αριθμών απασχόλησε από τους αρχαίους χρόνους τους μαθηματικούς.Ο Ερατοσθένης ένας σπουδαίος Έλληνας μαθηματικός που έζησε περίπου το 250 π.Χ., επινόησε μια μέθοδο για την εύρεση της ακολουθίας των πρώτων αριθμών που είναι μικρότεροι του ν. Την μέθοδο αυτή την  χρησιμοποιούμε μέχρι και σήμερα και είναι γνωστή ως το «Κόσκινο του Ερατοσθένη». 

 Η διαδικασία είναι απλή και είναι ουσιαστικά ένας αλγόριθμος που μας επιτρέπει να βρούμε πρώτους αριθμούς ακολουθώντας βήματα. Περιγράφεται ως εξής:

Αλγόριθμος Εύρεσης Πρώτων Αριθμών:

1) Τοποθετούμε σε έναν πίνακα όσους φυσικούς αριθμούς θέλουμε, έστω ν.

2) Στο σύνολο των φυσικών αριθμών, κρατάμε τον αριθμό 2 που είναι πρώτος και ξεκινάμε και διαγράφουμε τα πολλαπλάσια του 2 που είναι το 4, το 6, το 8, κ.τ.λ. επειδή και αυτοί  ως πολλαπλάσια του 2 δεν είναι πρώτοι αριθμοί. 

Αμέσως μετά, κάνουμε το ίδιο με τον αριθμό 3, που είναι ο επόμενος μικρότερος πρώτος αριθμός που δεν έχει διαγραφεί. Διαγράφουμε δηλαδή όλα το πολλαπλάσια του 3, που είναι το 6, το 9, το 12 κ.τ.λ..

Συνεχίζουμε με αυτόν τον τρόπο το «κοσκίνισμα» ,διαγράφοντας διαδοχικά όλα τα πολλαπλάσια του μικρότερου επόμενου αριθμού  του επόμενου μη διαγραμμένου αριθμό. διαγράφουμε πρώτα τα πολλαπλάσια του 2, μετά διαγράφουμε τα πολλαπλάσια

3) Οι αριθμοί που θα απομείνουν είναι όλοι πρώτοι αριθμοί.

!!! Είναι προφανές ότι η παραπάνω διαδικασία δεν μπορεί να εφαρμοστεί σε όλο το σύνολο των φυσικών αριθμών, αλλά σε ένα υποσύνολο της μορφής {2, 3, 4, 5, ..., ν} όπου ν οποιοσδήποτε φυσικός αριθμός.