Οι πρώτοι αριθμοί αποτελούν θεμελιώδες κομμάτι των μαθηματικών, αλλά πώς μπορούμε να τους βρούμε γρήγορα σε ένα συγκεκριμένο διάστημα; Μία από τις πιο κλασικές και αποδοτικές μεθόδους είναι το Κόσκινο του Ερατοσθένη, το οποίο επινοήθηκε από τον αρχαίο Έλληνα μαθηματικό Ερατοσθένη.
🔹 Η Ιδέα της Μεθόδου
Η βασική ιδέα του κόσκινου είναι να ξεκινήσουμε με όλους τους αριθμούς ενός διαστήματος και να διαγράψουμε σταδιακά τους σύνθετους αριθμούς, αφήνοντας στο τέλος μόνο τους πρώτους.
📌 Βήματα της Μεθόδου:
- Γράφουμε όλους τους αριθμούς από το $2$ έως έναν μέγιστο αριθμό $N$.
- Επιλέγουμε τον μικρότερο αριθμό που δεν έχει διαγραφεί (ο οποίος είναι πρώτος).
- Διαγράφουμε όλα τα πολλαπλάσιά του (καθώς είναι σύνθετα).
- Επαναλαμβάνουμε τα βήματα $2-3$ μέχρι να περάσουμε τη $\sqrt{N}$.
- Οι αριθμοί που απομένουν είναι πρώτοι.
🔹 Παράδειγμα: Εύρεση των πρώτων αριθμών στο διάστημα [100,200]
Εφαρμόζουμε το Κόσκινο του Ερατοσθένη στο διάστημα $[100,200]$ και διαγράφουμε τους σύνθετους αριθμούς.
📌 Αρχικά έχουμε όλους τους αριθμούς:
$100,101,102,…,200$
📌 Διαγράφουμε τα πολλαπλάσια των πρώτων αριθμών:
- $p=2⇒$ Διαγράφουμε $102,104,106,…102, 104, 106, \dots$$
- $p=3⇒$ Διαγράφουμε $102,105,108,…102, 105, 108, \dots$
- $p=5⇒$ Διαγράφουμε $100,105,110,…100, 105, 110, \dots$
- $p=7⇒$ Διαγράφουμε $105,112,119,…$
📌 Οι αριθμοί που απομένουν είναι οι πρώτοι στο διάστημα:
101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου