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

Ο Ερατοσθένης (Κυρήνη 276 π.Χ. – Αλεξάνδρεια 194 π.Χ.) ήταν αρχαίος Έλληνας μαθηματικός, γεωγράφος, αστρονόμος, γεωδαίτης, ιστορικός και φιλόλογος. Θεωρείται ο πρώτος που υπολόγισε το μέγεθος της Γης και κατασκεύασε ένα σύστημα συντεταγμένων με παράλληλους και μεσημβρινούς. Ακόμα κατασκεύασε ένα χάρτη του κόσμου όπως τον θεωρούσε. Για τις θεωρίες του περί γεωγραφίας κατηγορήθηκε αργότερα από τον Στράβωνα, ότι δεν παρείχε τις αναγκαίες αποδείξεις.

Ερατοσθένης ο Κυρηναίος ανακάλυψε μια μέθοδο για να υπολογίζει τους πρώτους αριθμούς. Το ‘κόσκινό’ του ήταν μια σπουδαία ανακάλυψη για την εποχή του και ένα από τα μεγάλα επιτεύγματα του σημαντικού αυτού προσώπου.

Ο αλγόριθμος εμφανίζει όλους τους πρώτους αριθμούς από το 2 (1ος πρώτος) μέχρι ένα δεδομένο ακέραιο n. Εμφανίζουμε το 2 και διαγράφουμε όλα τα πολλαπλάσιά του. Στη συνέχεια εμφανίζουμε τον επόμενο διαθέσιμο αριθμό και διαγράφουμε όλα τα πολλαπλάσιά του. Η διαδικασία επαναλαμβάνεται μέχρι το τετράγωνο κάποιου αριθμού που εμφανίσαμε να ξεπερνά το n. Και όλοι οι υπόλοιποι αριθμοί που δεν διαγράφηκαν είναι πρώτοι.

Το κόσκινο του Ερατοσθένη σε ψευδογλώσσα:

Αλγόριθμος ΤοΚόσκινοΤουΕρατοσθένη
 Αρχή_επανάληψης
  Διάβασε n
 μέχρις_ότου n>1
 Για i από 2 μέχρι n
  Α[i]  ΑΛΗΘΗΣ
 Τέλος_επανάληψης
 Για i από 2 μέχρι Τ_Ρ(n) !Τετραγωνική Ρίζα του n
  Αν Α[i]=ΑΛΗΘΗΣ τότε
   j  i^2
   λ  1
   Όσο j<=n επανάλαβε
    Α[j]  ΨΕΥΔΗΣ
    j  i^2+λ*i
    λ  λ+1
   Τέλος_επανάληψης
  Τέλος_αν
 Τέλος_επανάληψης
 Για i από 2 μέχρι n
  Αν Α[i]=ΑΛΗΘΗΣ τότε
   Εμφάνισε i
  Τέλος_αν
 Τέλος_επανάληψης
Τέλος ΤοΚόσκινοΤουΕρατοσθένη
Advertisement