Ο αλγόριθμος που επινόησε ο αλεξανδρινός μαθηματικός Ερατοσθένης (275-195 π.Χ.) για την εύρεση όλων των πρώτων αριθμών (αριθμοί που διαιρούνται ακριβώς μόνο από τον εαυτό τους και τη μονάδα) από το 1 έως το η (όπου η οποιοσδήποτε φυσικός αριθμός).
Κατά τον αλγόριθμο αυτό, χρησιμοποιούνται όλοι οι αριθμοί από το 2 μέχρι και το η και η διαδικασία ξεκινά με το 2 και τη διαγραφή όλων των πολλαπλασίων του. Ύστερα ακολουθεί το 3, όπου και τα πολλαπλάσια αυτού διαγράφονται, στη συνέχεια διαγράφονται τα πολλαπλάσια του 5 (αφού το 4 έχει ήδη διαγραφεί ως πολλαπλάσιο του 2) κ.ο.κ. όσο δεν ξεπερνάτε ο αριθμός V--n
Οι αριθμοί που απομένουν στο τέλος είναι οι ζητούμενοι.
Πιο αναλυτικά, ο αλγόριθμος έχει τα ακόλουθα τέσσερα βήματα:
α) Γραφή με τη σειρά της κύριας λίστας με τους αριθμούς από το 2 μέχρι και το η
β) μεταφορά του πρώτου αριθμού που συναντάται στην κύρια λίστα στη λίστα των πρώτων
γ) διαγραφή όλων των πολλαπλασίων αυτού του αριθμού από την κύρια λίστα
δ) αν ο μικρότερος αριθμός της κύριας λίστας είναι μικρότερος από το [v--n] ακολουθείται το βήμα 2, αλλιώς όλοι οι εναπομείναντες αριθμοί της κύριας λίστας μεταφέρονται στη λίστα των πρώτων και ο αλγόριθμος τερματίζει.
Στο παράδειγμα αυτό προκύπτει ο τρόπος με τον οποίο λειτουργεί το κόσκινο του Ερατοσθένη για η = 100.
Ο αλγόριθμος χρειάζεται τέσσερις επαναλήψεις, για να βρει όλους τους πρώτους αριθμούς από το 1 έως το 100.
Κατά την πρώτη επανάληψη λαμβάνεται ο αριθμός 2 και διαγράφονται όλα τα πολλαπλάσιά του.
Στη δεύτερη (αντίστοιχα τρίτη) επανάληψη εμφανίζεται ο αριθμός 3 (αντίστοιχα 5) και διαγράφονται όλα τα πολλαπλάσιά του από τους εναπομείναντες αριθμούς.
Τέλος στην τέταρτη επανάληψη γίνεται το ίδιο και με το 7, αλλά επειδή = v--100=10 < 11 ο αλγόριθμος τερματίζει.
Έτσι, οι πρώτοι αριθμοί από το 1 έως το 100 είναι οι: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97.
Πιο αναλυτικά, ο αλγόριθμος έχει τα ακόλουθα τέσσερα βήματα:
α) Γραφή με τη σειρά της κύριας λίστας με τους αριθμούς από το 2 μέχρι και το η
β) μεταφορά του πρώτου αριθμού που συναντάται στην κύρια λίστα στη λίστα των πρώτων
γ) διαγραφή όλων των πολλαπλασίων αυτού του αριθμού από την κύρια λίστα
δ) αν ο μικρότερος αριθμός της κύριας λίστας είναι μικρότερος από το [v--n] ακολουθείται το βήμα 2, αλλιώς όλοι οι εναπομείναντες αριθμοί της κύριας λίστας μεταφέρονται στη λίστα των πρώτων και ο αλγόριθμος τερματίζει.
Στο παράδειγμα αυτό προκύπτει ο τρόπος με τον οποίο λειτουργεί το κόσκινο του Ερατοσθένη για η = 100.
Ο αλγόριθμος χρειάζεται τέσσερις επαναλήψεις, για να βρει όλους τους πρώτους αριθμούς από το 1 έως το 100.
Κατά την πρώτη επανάληψη λαμβάνεται ο αριθμός 2 και διαγράφονται όλα τα πολλαπλάσιά του.
Στη δεύτερη (αντίστοιχα τρίτη) επανάληψη εμφανίζεται ο αριθμός 3 (αντίστοιχα 5) και διαγράφονται όλα τα πολλαπλάσιά του από τους εναπομείναντες αριθμούς.
Τέλος στην τέταρτη επανάληψη γίνεται το ίδιο και με το 7, αλλά επειδή = v--100=10 < 11 ο αλγόριθμος τερματίζει.
Έτσι, οι πρώτοι αριθμοί από το 1 έως το 100 είναι οι: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97.
Κόσκινο 2_320x240.jpg
