Το Κόσκινο του Ερατοσθένη: Η Κλασική Μέθοδος για την Εύρεση Πρώτων Αριθμών

Οι πρώτοι αριθμοί αποτελούν θεμελιώδες κομμάτι των μαθηματικών, αλλά πώς μπορούμε να τους βρούμε γρήγορα σε ένα συγκεκριμένο διάστημα; Μία από τις πιο κλασικές και αποδοτικές μεθόδους είναι το Κόσκινο του Ερατοσθένη, το οποίο επινοήθηκε από τον αρχαίο Έλληνα μαθηματικό Ερατοσθένη.

---

🔹 Η Ιδέα της Μεθόδου

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

📌 Βήματα της Μεθόδου:

1. Γράφουμε όλους τους αριθμούς από το $2$ έως έναν μέγιστο αριθμό $N$.
2. Επιλέγουμε τον μικρότερο αριθμό που δεν έχει διαγραφεί (ο οποίος είναι πρώτος).
3. Διαγράφουμε όλα τα πολλαπλάσιά του (καθώς είναι σύνθετα).
4. Επαναλαμβάνουμε τα βήματα $2-3$ μέχρι να περάσουμε τη $\sqrt{N}$.
5. Οι αριθμοί που απομένουν είναι πρώτοι.

---

🔹 Παράδειγμα: 

Εύρεση των πρώτων αριθμών στο διάστημα [100,200]

Εφαρμόζουμε το Κόσκινο του Ερατοσθένη στο διάστημα $[100,200]$ και διαγράφουμε τους σύνθετους αριθμούς.

📌 Αρχικά έχουμε όλους τους αριθμούς:

$100,101,102,\dots ,200$

📌 Διαγράφουμε τα πολλαπλάσια των πρώτων αριθμών:

• $p=2\Rightarrow$ Διαγράφουμε $102,104,106,\dots 102,104,106,\dots$$
• $p=3\Rightarrow$ Διαγράφουμε $102,105,108,\dots 102,105,108,\dots$
• $p=5\Rightarrow$ Διαγράφουμε $100,105,110,\dots 100,105,110,\dots$
• $p=7\Rightarrow$ Διαγράφουμε $105,112,119,\dots$

📌 Οι αριθμοί που απομένουν είναι οι πρώτοι στο διάστημα:

101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199