Ο Ερατοσθένης (Κυρήνη 276 π.Χ. – Αλεξάνδρεια 194 π.Χ.) ήταν αρχαίος Έλληνας μαθηματικός, γεωγράφος και αστρονόμος. Θεωρείται ο πρώτος που υπολόγισε το μέγεθος της Γης και κατασκεύασε ένα σύστημα συντεταγμένων με παράλληλους και μεσημβρινούς. Ακόμα κατασκεύασε ένα χάρτη του κόσμου όπως τον θεωρούσε. Για τις θεωρίες του περί γεωγραφίας κατηγορήθηκε αργότερα από τον Στράβωνα, ότι δεν παρείχε τις αναγκαίες αποδείξεις.
Βιογραφία
Αν και ο Ερατοσθένης γεννήθηκε στην Κυρήνη (στη σημερινή Λιβύη), έζησε, εργάστηκε και πέθανε στην Αλεξάνδρεια, πρωτεύουσα της πτολεμαϊκής Αιγύπτου.
Σπούδασε στην Αλεξάνδρεια και ισχυριζόταν ότι επίσης σπούδασε για κάποια χρόνια στην Αθήνα. Το 236 π.Χ. ορίστηκε από τον Πτολεμαίο τον Γ΄ τον Ευεργέτη βιβλιοθηκάριος της βιβλιοθήκης της Αλεξάνδρειας, διαδεχόμενος τον Ζηνόδοτο.
Δεν παντρεύτηκε ποτέ. Το 194 π.Χ. τυφλώθηκε και ένα χρόνο αργότερα σταμάτησε να τρώει και πέθανε.
Το έργο του
Έκανε αρκετές σημαντικές συνεισφορές στα Μαθηματικά και ήταν φίλος του σπουδαίου μαθηματικού Αρχιμήδη. Γύρω στο 225 π.Χ. εφηύρε τον σφαιρικό αστρολάβο, που τον χρησιμοποιούσαν ευρέως μέχρι την εφεύρεση του πλανηταρίου τον 18ο αιώνα.
Αναφέρεται από τον Κλεομήδη στο Περί της κυκλικής του κινήσεως των ουρανίων σωμάτων ότι γύρω στο 240 π.Χ. υπολόγισε την περιφέρεια της Γης χρησιμοποιώντας το ύψος του Ηλίου κατά το θερινό ηλιοστάσιο σε δύο διαφορετικά γεωγραφικά σημεία, που όμως βρίσκονταν στον ίδιο (περίπου) μεσημβρινό: κοντά στην Αλεξάνδρεια και στη νήσο Ελεφαντίνη -όπου ο Ήλιος ήταν στο ζενίθ του ουρανού- κοντά στη Συήνη (σημερινό Ασουάν, Αίγυπτος).
Ο Ερατοσθένης υπολόγισε την περιφέρεια της Γης σε 252.000 στάδια. Δεν ξέρουμε όμως την ακρίβεια της μέτρησης, καθώς δεν ξέρουμε ποιο είδος σταδίου χρησιμοποίησε. Αν χρησιμοποίησε το αττικό στάδιο (184,98 μέτρα) τότε υπολόγισε την περιφέρεια σε 46.615 χιλιόμετρα. Αν χρησιμοποίησε το οδοιπορικό στάδιο (157,50 μέτρα) τότε την υπολόγισε σε 39.690 χιλιόμετρα που είναι αρκετά καλός υπολογισμός, με δεδομένο ότι σήμερα υπολογίζεται σε 40.007,86 χιλιόμετρα, ενώ στη Γαλλική Επανάσταση είχε οριστεί να είναι 40.000 χιλιόμετρα.
Ήταν ο πρώτος που υποστήριξε ότι η Γη είναι μια σφαίρα που βρίσκεται στο κέντρο του σύμπαντος, το οποίο περιστρέφεται με συχνότητα εικοσιτεσσάρων ωρών. Επινόησε επίσης το σύστημα των γεωγραφικών παραλλήλων. Διατύπωσε δε την υπόθεση, ότι είναι δυνατόν να ταξιδέψουμε κατά μήκος μιας γεωγραφικής παράλληλου ξεκινώντας από την Ιβηρία και να φτάσουμε έως την Ινδία, διαπλέοντας τον Ατλαντικό ωκεανό. Ο Στράβων που διέσωσε και μας μετέφερε την θεωρία αυτή, προσέθεσε μάλιστα, ότι στο ταξίδι αυτό ίσως να συναντούσαμε νέα άγνωστα μέρη ξηράς.
Επίσης εφηύρε έναν τρόπο υπολογισμού των πρώτων αριθμών γνωστό ως κόσκινο του Ερατοσθένη.
Ο όρος Γεωγραφία αποδίδεται στον Ερατοσθένη.
Το Κόσκινο του Ερατοσθένη
Στα μαθηματικά, το Κόσκινο του Ερατοσθένη είναι ένας απλός αλγόριθμος για την εύρεση όλων των πρώτων αριθμών μέχρι έναν συγκεκριμένο ακέραιο. Σαν αλγόριθμος είναι γρήγορος για μικρούς πρώτους (κάτω από 10 εκατομμύρια). Δημιουργήθηκε από τον Ερατοσθένη, μαθηματικό της Αρχαίας Ελλάδας. Αν και κανένα από τα μαθηματικά του έργα δεν έχει διασωθεί, το κόσκινο περιγράφεται και αποδίδεται στον Ερατοσθένη στην Εισαγωγή στην Αριθμητική του Νικόμαχου.
Αλγόριθμος
Ένας πρώτος αριθμός είναι ένας φυσικός αριθμός που έχει ακριβώς δύο διαφορετικούς διαιρέτες: το 1 και τον εαυτό του.
Η εύρεση όλων των πρώτων αριθμών που είναι μικρότεροι ή ίσοι από έναν ακέραιο n, σύμφωνα με τη μέθοδο του Ερατοσθένη, γίνεται ως εξής:
- Δημιουργούμε μια λίστα από διαδοχικούς ακέραιους από το 2 μέχρι το n: (2, 3, 4, ..., n).
- Αρχικά, έστω ότι το p είναι ίσο με 2, τον 1ο πρώτο αριθμό.
- Διαγράφουμε από τη λίστα όλα τα πολλαπλάσια του p που είναι μικρότερα ή ίσα με n. (2p, 3p, 4p, κτλ)
- Βρίσκουμε τον 1ο αριθμό που απομένει στη λίστα μετά τον p (αυτός ο αριθμός είναι ο επόμενος πρώτος αριθμός) και αντικαθιστούμε το p με αυτόν τον αριθμό.
- Επαναλαμβάνουμε τα βήματα 3 και 4 μέχρι το p2 να είναι μεγαλύτερο από n.
- Όλοι οι αριθμοί που απομένουν στη λίστα είναι πρώτοι αριθμοί.
Παράδειγμα
Για να βρούμε όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από το 30, εργαζόμαστε ως εξής:
Αρχικά δημιουργούμε μια λίστα από τους ακέραιους από το 2 έως το 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Διαγράφουμε τα πολλαπλάσια του 2 με αποτέλεσμα:
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Ο 1ος αριθμός στη λίστα μετά το 2 είναι το 3 και διαγράφουμε τα πολλαπλάσια του 3 από τη λίστα με αποτέλεσμα:
2 3 5 7 11 13 17 19 23 25 29
Ο 1ος αριθμός στη λίστα μετά το 3 είναι το 5 και διαγράφουμε τα πολλαπλάσια του 5 από τη λίστα με αποτέλεσμα:
2 3 5 7 11 13 17 19 23 29
Ο 1ος αριθμός στη λίστα μετά το 5 είναι το 7 αλλά το τετράγωνο του 7 είναι 49 που είναι μεγαλύτερο από το 30, επομένως η διαδικασία τελείωσε. Η τελική λίστα αποτελείται από όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από 30.
Πολυπλοκότητα αλγορίθμου και υλοποίηση
Η διαγραφή των πολλαπλασίων κάθε πρώτου αριθμού που εντοπίζεται μπορεί να αρχίζει από το τετράγωνο κάποιου αριθμού, μιας και τα μικρότερα πολλαπλάσια έχουν ήδη διαγραφεί σε προηγούμενα βήματα.
Η πολυπλοκότητα του αλγορίθμου είναι 
λειτουργίες bit με απαιτήσεις μνήμης 
. Η χρονική πολυπλοκότητα στο μοντέλο μηχανής RAM είναι 
λειτουργίες, κάτι που προκύπτει κατευθείαν από το ότι η αρμονική σειρά πρώτων (prime harmonic series) τείνει ασυμπτωτικά στο 1/(ln(ln(N))). Η κατακερματισμένη έκδοση του κόσκινου του Ερατοσθένη, με βασικές βελτιστοποιήσεις, χρησιμοποιεί λειτουργίες και 
bits μνήμης.
λειτουργίες bit με απαιτήσεις μνήμης . Η χρονική πολυπλοκότητα στο μοντέλο μηχανής RAM είναι λειτουργίες, κάτι που προκύπτει κατευθείαν από το ότι η αρμονική σειρά πρώτων (prime harmonic series) τείνει ασυμπτωτικά στο 1/(ln(ln(N))). Η κατακερματισμένη έκδοση του κόσκινου του Ερατοσθένη, με βασικές βελτιστοποιήσεις, χρησιμοποιεί λειτουργίες και bits μνήμης.
Το 1975, ο Ντέιβιντ Τέρνερ (David Turner) πρότεινε ότι το κόσκινο των πρώτων αριθμών μπορεί να αναπαρασταθεί με έναν πολύ απλό και κομψό τρόπο, χρησιμοποιώντας αμιγώς συναρτησιακές γλώσσες προγραμματισμού. Το κόσκινο του Τέρνερ, που μοιάζει αρκετά με το κόσκινο του Όιλερ παρακάτω, υλοποιείται σε Haskell ως εξής:
primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
Το 2008, η Μελίσα Ο'Νιλ (Melissa O'Neill) έδειξε ότι η πολυπλοκότητα του αλγορίθμου του Turner είναι σημαντικά χειρότερη από την πολυπλοκότητα των κλασικών προστακτικών εκδόσεων του κόσκινου. Η Ο'Νιλ έδειξε μια έκδοση του κόσκινου του Ερατοσθένη σε Haskell με τη χρήση ουρών προτεραιότητας (priority queues) που έχει πολυπλοκότητα παρόμοια με αυτή των κλασικών προστακτικών υλοποιήσεων.
Το Κόσκινο του Όιλερ
Ο Όιλερ, στην απόδειξή του για το γινόμενο Όιλερ της ζ-συνάρτησης του Ρίμαν, χρησιμοποίησε μια έκδοση του κόσκινου του Ερατοσθένη, η οποία ήταν καλύτερη γιατί κάθε αριθμός απαλειφόταν ακριβώς μια φορά. Σε αντίθεση με το κόσκινο του Ερατοσθένη που διαγράφει πολλαπλάσια των πρώτων αριθμών που βρίσκει από την ίδια ακολουθία, το κόσκινο του Όιλερ χρησιμοποιεί ακολουθίες που έχουν δημιουργηθεί διαδοχικά από πολλαπλάσια των προηγούμενων πρώτων αριθμών:
Α) Αρχίζουμε με όλους τους φυσικούς αριθμούς εκτός από το '1' που δεν είναι πρώτος αριθμός:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...
^
Β) Ο αριθμός στα αριστερά είναι πρώτος. Πολλαπλασιάζουμε κάθε αριθμό
στη λίστα με αυτόν και αγνοούμε τα γινόμενα:
(4 6 8 10 12 14 16 18 20 22 24 26 28 30 ... )
Διαγράφονται:
4 6 8 10 12 14 16 18 20 22 24 26 28 30
Παραμένουν:
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 ...
^
Γ) Ο αριθμός πριν τον προηγούμενο πρώτο είναι επίσης πρώτος. Πολλαπλασιάζουμε με αυτόν κάθε
αριθμό στη λίστα αρχίζοντας από αυτόν τον πρώτο και αγνοούμε τα γινόμενα:
(9 15 21 27 33 39 45 51 57 63 69 75 81 87 ...)
Αφαιρούνται:
9 15 21 27
Παραμένουν:
2 3 5 7 11 13 17 19 23 25 29 ...
^
Επαναλαμβάνουμε το Γ) επ' άπειρον. Σε κάθε επανάληψη εντοπίζουμε έναν νέο πρώτο αριθμό (που μαρκάρεται με το δείκτη , ^) μέχρι να βρεθούν όλοι οι πρώτοι στην αρχική λίστα. Πρέπει να σημειωθεί ότι οι αριθμοί που απορρίπτονται εξακολουθούν να χρησιμοποιούνται για την κατασκευή του τρέχοντος κόσκινου, δηλ. όταν κατασκευάζουμε ένα κόσκινο για το 3 κάνουμε τις πράξεις 3*3=9, 3*5=15, 3*7=21, ... 3*15=45, ... Το 15 που απορρίπτεται χρησιμοποιείται για την κατασκευή του κόσκινου και μετά οι αριθμοί αφαιρούνται από τη λίστα.
Το κόσκινο του Όιλερ είναι μια καλή λύση για την παραγωγή άπειρων ακολουθιών πρώτων αριθμών και το κόσκινο του Τέρνερ είναι μια κοντινή εκδοχή του.
Σε Haskell γράφεται:
import Data.OrdList (minus)
primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))
Σε Python:
def euler_sieve(n):
# δημιουργεί έναν πίνακα από περιττούς αριθμούς.
num_tab = range(1,n,2)
# ο πίνακας είναι ο 1,3,5,7,... αλλάζουμε το 1ο στοιχείο
# στον πρώτο αριθμό, 2
num_tab[0] = 2
i = 1
# ο μεγαλύτερος αριθμός στον πίνακα
highestval = num_tab[-1]
while True:
# βρες τον 1ο τελεστή στο κόσκινο
cx = num_tab[i]
# αν τιμή που δε δουλεύει, προχώρησε στην επόμενη
if cx == False:
i += 1
continue
# η 1η τιμή που περνάει από το κόσκινο είναι πάντα ο
# τρέχων αριθμός * τον εαυτό του. όλοι οι άλλοι αριθμοί
# στο κόσκινο θα είναι μεγαλύτεροι.
if cx**2 > n:
break
# διαγράφει - κόσκινο
tostrike = []
for j in xrange(i,len(num_tab)):
# βρίσκει τον 2ο τελεστή στο κόσκινο
cy = num_tab[j]
# αν τιμή που δε δουλεύει, αγνόησε τα υπόλοιπα
if cy == False:
continue
cut = cx*cy
# εκτός των ορίων του κόσκινου
if cut > highestval:
break
# προσθέτει στο κόσκινο
tostrike.append(cut)
# περνάει από το κόσκινο τις τιμές από τον πίνακα των αριθμών μας
for d in tostrike:
ind = (d - 1)/2
num_tab[ind] = False
# βρίσκει τη μεγαλύτερη τιμή στον πίνακα που δεν
# έχει περάσει από το κόσκινο
hiind = -1
while num_tab[hiind] == False:
hiind -= 1
highestval = num_tab[hiind]
i += 1
return num_tab
...
print [x for x in euler_sieve(100) if x != False]
Στον αλγόριθμο αυτό, σε σύγκριση με τον αλγόριθμο που χρησιμοποιεί ο Όιλερ στην απόδειξή του, οι πρώτοι αριθμοί αριστερά του δείκτη αντιστοιχούν σε παράγοντες του αριστερού μέλους της εξίσωσης σε κάθε στάδιο του κόσκινου, ενώ η ακολουθία στα δεξιά, μαζί με τη θέση του δείκτη, αντιστοιχεί στη σειρά του δεξιού μέλους της εξίσωσης σε κάθε στάδιο (εκτός από το αρχικό).
Όταν παράγουμε μια πεπερασμένη λίστα πρώτων, όταν ξεπεράσουμε το τετράγωνο του άνω ορίου του εύρους μας, έχουμε την επιθυμητή ακολουθία πρώτων αριθμών. Στο παραπάνω παράδειγμα, αυτό συμβαίνει όταν εντοπίζουμε τον πρώτο αριθμό 7, για να βρούμε τη λίστα όλων των πρώτων αριθμών μέχρι το 30.
Η μέτρηση της περιφέρειας της γης από τον Ερατοσθένη
Ένα από τα πιο σημαντικά πειράματα που πραγματοποιήθηκε στην ιστορία της ανθρωπότητας ήταν η μέτρηση της περιφέρειας της γης από τον Ερατοσθένη τον 3 π.Χ. αιώνα. Ο Ερατοσθένης πληροφορήθηκε ότι στη Συήνη (σημερινό Ασουάν) ο ήλιος κατά το μεσημέρι του θερινού ηλιοστασίου ρίχνει τις ακτίνες του κάθετα στον ορίζοντα και φωτίζει τον πυθμένα ενός πηγαδιού. Την ίδια στιγμή στην Αλεξάνδρεια οι ακτίνες του ηλίου σχηματίζουν μια γωνία 7ο με την κατακόρυφο του τόπου. Στη συνέχεια μέτρησε την απόσταση Αλεξάνδρειας - Συήνης και υπολόγισε, όπως φαίνεται στο σχήμα που ακολουθεί, με αξιοζήλευτη ακρίβεια την περιφέρεια της γης.