Κυριακή 26 Απριλίου 2026

Κόσκινο του Ερατοσθένη – Πλήρης Οδηγός με Αλγόριθμο σε ΓΛΩΣΣΑ (ΑΕΠΠ)

🔍 Κόσκινο του Ερατοσθένη – Πλήρης Οδηγός με Αλγόριθμο σε ΓΛΩΣΣΑ (ΑΕΠΠ)

Κόσκινο του Ερατοσθένη - Αλγόριθμος εύρεσης πρώτων αριθμών

Το Κόσκινο του Ερατοσθένη - Ένας από τους αρχαιότερους αλγόριθμους στην ιστορία (περ. 200 π.Χ.)

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

Σε αυτόν τον πλήρη οδηγό θα μάθουμε πώς λειτουργεί το Κόσκινο του Ερατοσθένη, θα το υλοποιήσουμε σε ΓΛΩΣΣΑ (ΑΕΠΠ), θα δούμε βελτιστοποιήσεις και θα αναλύσουμε πολλά παραδείγματα.

🔍 Τι είναι το Κόσκινο του Ερατοσθένη;

Το Κόσκινο του Ερατοσθένη είναι ένας αλγόριθμος που βρίσκει όλους τους πρώτους αριθμούς μέχρι ένα φυσικό αριθμό Ν. Η λέξη «κόσκινο» παραπέμπει σε ένα φίλτρο που «κοσκινίζει» τους αριθμούς, αφαιρώντας αυτούς που δεν είναι πρώτοι.

Η βασική ιδέα είναι απλή:

Γράφουμε όλους τους αριθμούς από το 2 μέχρι το Ν.
Ξεκινάμε από τον μικρότερο πρώτο (το 2) και «διαγράφουμε» όλα τα πολλαπλάσιά του.
Προχωράμε στον επόμενο αριθμό που δεν έχει διαγραφεί (είναι πρώτος) και επαναλαμβάνουμε.
Στο τέλος, οι αριθμοί που δεν διαγράφηκαν είναι οι πρώτοι αριθμοί.

⚙️ 2. Πώς λειτουργεί – Βήμα-βήμα

Ας δούμε τη διαδικασία για Ν = 30:

Βήμα	Ενέργεια	Κατάσταση
1	Γράφουμε όλους τους αριθμούς 2,3,4,...,30	[2,3,4,5,6,7,8,9,10,...,30]
2	Πρώτος πρώτος = 2. Διαγράφουμε πολλαπλάσια: 4,6,8,10,12,14,16,18,20,22,24,26,28,30	[2,3,4,5,6,7,8,9,10,11,...]
3	Επόμενος μη διαγεγραμμένος = 3. Διαγράφουμε πολλαπλάσια: 9,15,21,27	[2,3,4,5,6,7,8,9,10,11,...]
4	Επόμενος = 5. Διαγράφουμε πολλαπλάσια: 25	Διαγράφεται το 25
5	Επόμενος = 7. 7²=49 > 30 → ΤΕΛΟΣ	Οι υπόλοιποι είναι πρώτοι

✅ Αποτέλεσμα: Πρώτοι αριθμοί μέχρι το 30 είναι: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

🔑 Βασική παρατήρηση: Μπορούμε να σταματήσουμε τη διαδικασία όταν ο τρέχων πρώτος p ικανοποιεί p² > N. Γιατί; Κάθε σύνθετος αριθμός ≤ N έχει έναν πρώτο παράγοντα ≤ √N.

📝 3. Αλγόριθμος σε ΓΛΩΣΣΑ (ΑΕΠΠ)

💻 Βασική Υλοποίηση

Πρόγραμμα Κοσκινο_Ερατοσθένη
Μεταβλητές
  Ακέραιες: Ν, i, j
  Λογικές: πρώτος[1000]   ! πίνακας για μέχρι 1000 αριθμούς
Αρχή
  Διάβασε Ν

  ! Αρχικοποίηση: όλοι οι αριθμοί θεωρούνται πρώτοι
  Για i από 2 μέχρι Ν
    πρώτος[i] ← Αληθής
  Τέλος_επανάληψης

  ! Κόσκινο
  i ← 2
  Όσο i*i <= Ν επανάλαβε
    Αν πρώτος[i] = Αληθής τότε
      ! Διαγραφή πολλαπλασίων του i
      j ← i*i
      Όσο j <= Ν επανάλαβε
        πρώτος[j] ← Ψευδής
        j ← j + i
      Τέλος_επανάληψης
    Τέλος_αν
    i ← i + 1
  Τέλος_επανάληψης

  ! Εμφάνιση αποτελεσμάτων
  Γράψε "Πρώτοι αριθμοί μέχρι το ", Ν, ":"
  Για i από 2 μέχρι Ν
    Αν πρώτος[i] = Αληθής τότε
      Γράψε i, " "
    Τέλος_αν
  Τέλος_επανάληψης

Τέλος_Προγράμματος

💻 Βελτιστοποιημένη έκδοση (με δυναμικά όρια)

Πρόγραμμα Κοσκινο_Βελτιστοποιημένο
Μεταβλητές
  Ακέραιες: Ν, i, j
  Λογικές: πρώτος[10000]   ! μέχρι 10000
Αρχή
  Διάβασε Ν

  ! Όλοι θεωρούνται πρώτοι
  Για i από 2 μέχρι Ν
    πρώτος[i] ← Αληθής
  Τέλος_επανάληψης

  ! Μόνο μέχρι τετραγωνική ρίζα
  i ← 2
  Όσο i*i <= Ν επανάλαβε
    Αν πρώτος[i] = Αληθής τότε
      ! Ξεκινάμε από i*i (τα μικρότερα έχουν ήδη διαγραφεί)
      j ← i*i
      Όσο j <= Ν επανάλαβε
        πρώτος[j] ← Ψευδής
        j ← j + i
      Τέλος_επανάληψης
    Τέλος_αν
    i ← i + 1
  Τέλος_επανάληψης

  ! Εμφάνιση
  Γράψε "Πρώτοι: "
  Για i από 2 μέχρι Ν
    Αν πρώτος[i] = Αληθής τότε
      Γράψε i, " "
    Τέλος_αν
  Τέλος_επανάληψης

Τέλος_Προγράμματος

🔑 Σημαντική σημείωση: Στη ΓΛΩΣΣΑ, οι λογικοί πίνακες δηλώνονται με Λογικές: όνομα[διάσταση]. Το μέγεθος του πίνακα πρέπει να είναι γνωστό κατά τη μεταγλώττιση.

📊 4. Αναλυτικό Παράδειγμα (μέχρι 30)

Ας εκτελέσουμε τον αλγόριθμο βήμα-βήμα για Ν = 30:

i	Είναι πρώτος;	Διαγράφονται	Υπόλοιποι
2	✅	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
3	✅	9,15,21,27	2,3,5,7,11,13,17,19,23,25,29
4	❌ (διαγράφηκε)	-	-
5	✅	25	2,3,5,7,11,13,17,19,23,29
6	❌	-	-
7	✅	7²=49 > 30 → ΤΕΛΟΣ	2,3,5,7,11,13,17,19,23,29

✅ Οι πρώτοι αριθμοί μέχρι το 30 είναι: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

⚡ 5. Βελτιστοποιήσεις

Ο αλγόριθμος του Ερατοσθένη μπορεί να βελτιστοποιηθεί περαιτέρω:

Βελτιστοποίηση	Περιγραφή	Κέρδος
Έναρξη από i²	Τα μικρότερα πολλαπλάσια έχουν ήδη διαγραφεί	Λιγότερες επαναλήψεις
Όριο μέχρι √N	Αν i² > N, σταματάμε	Τεράστιο κέρδος για μεγάλα Ν
Παράβλεψη άρτιων	Επεξεργαζόμαστε μόνο περιττούς	Μείωση μνήμης και χρόνου ~50%
Τμηματικό κόσκινο	Χωρίζουμε σε τμήματα για πολύ μεγάλα Ν	Εξοικονόμηση μνήμης

📌 Παρατήρηση: Για τις εξετάσεις ΑΕΠΠ, αρκεί η βασική υλοποίηση με το όριο √N.

📈 6. Σύγκριση με άλλες μεθόδους

Μέθοδος	Πολυπλοκότητα	Πλεονεκτήματα	Μειονεκτήματα
Κόσκινο Ερατοσθένη	O(N log log N)	Πολύ γρήγορο, βρίσκει όλους τους πρώτους	Χρειάζεται μνήμη O(N)
Έλεγχος ενός αριθμού	O(√N)	Δεν χρειάζεται πίνακα	Αργό για πολλούς αριθμούς
Κόσκινο Atkins	O(N / log log N)	Πιο γρήγορο για πολύ μεγάλα Ν	Πιο πολύπλοκο

📌 Για το ΑΕΠΠ: Το Κόσκινο του Ερατοσθένη είναι η προτεινόμενη μέθοδος λόγω απλότητας και αποδοτικότητας.

✏️ 7. Ασκήσεις για εξάσκηση

🔢 Άσκηση 1

Να γραφεί αλγόριθμος σε ΓΛΩΣΣΑ που διαβάζει έναν αριθμό Ν και εμφανίζει όλους τους πρώτους αριθμούς από το 2 έως το Ν.

🔍 Δείτε τη λύση

Πρόγραμμα Άσκηση_1
Μεταβλητές
  Ακέραιες: Ν, i, j
  Λογικές: πρώτος[1000]
Αρχή
  Διάβασε Ν
  Για i από 2 μέχρι Ν
    πρώτος[i] ← Αληθής
  Τέλος_επανάληψης

  i ← 2
  Όσο i*i <= Ν επανάλαβε
    Αν πρώτος[i] = Αληθής τότε
      j ← i*i
      Όσο j <= Ν επανάλαβε
        πρώτος[j] ← Ψευδής
        j ← j + i
      Τέλος_επανάληψης
    Τέλος_αν
    i ← i + 1
  Τέλος_επανάληψης

  Για i από 2 μέχρι Ν
    Αν πρώτος[i] = Αληθής τότε
      Γράψε i
    Τέλος_αν
  Τέλος_επανάληψης
Τέλος_Προγράμματος

🔢 Άσκηση 2

Να τροποποιήσετε τον αλγόριθμο ώστε να εμφανίζει μόνο τους πρώτους αριθμούς που είναι μικρότεροι του 100 και να μετράει πόσοι είναι.

🔍 Δείτε τη λύση

Πρόγραμμα Άσκηση_2
Μεταβλητές
  Ακέραιες: i, j, πλήθος
  Λογικές: πρώτος[100]
Αρχή
  πλήθος ← 0
  Για i από 2 μέχρι 99
    πρώτος[i] ← Αληθής
  Τέλος_επανάληψης

  i ← 2
  Όσο i*i <= 99 επανάλαβε
    Αν πρώτος[i] = Αληθής τότε
      j ← i*i
      Όσο j <= 99 επανάλαβε
        πρώτος[j] ← Ψευδής
        j ← j + i
      Τέλος_επανάληψης
    Τέλος_αν
    i ← i + 1
  Τέλος_επανάληψης

  Για i από 2 μέχρι 99
    Αν πρώτος[i] = Αληθής τότε
      Γράψε i
      πλήθος ← πλήθος + 1
    Τέλος_αν
  Τέλος_επανάληψης

  Γράψε "Πλήθος πρώτων: ", πλήθος
Τέλος_Προγράμματος

✅ Αποτέλεσμα: 25 πρώτοι αριθμοί (2,3,5,7,11,...,97)

🏆 8. Γιατί είναι σημαντικός;

📜 Ιστορική σημασία: Είναι ένας από τους αρχαιότερους αλγόριθμους που χρησιμοποιούνται ακόμα.
⚡ Αποδοτικότητα: Πολυπλοκότητα O(N log log N) — σχεδόν γραμμική!
🔐 Κρυπτογραφία: Η εύρεση μεγάλων πρώτων είναι θεμελιώδης για το RSA.
💻 Αλγοριθμική σκέψη: Εξαιρετικό παράδειγμα βελτιστοποίησης και χρήσης πινάκων.
🎯 ΑΕΠΠ εξετάσεις: Συχνά ζητείται η υλοποίησή του σε θέματα 3 ή 4.

⚠️ 9. Συχνά λάθη

❌ Ξεκινάμε από 1: Το 1 δεν είναι πρώτος! Πάντα ξεκινάμε από το 2.
❌ Λάθος όρια στην επανάληψη: Το εξωτερικό loop είναι i*i <= N, όχι i <= N.
❌ Ξεκινάμε από 2i αντί για i²: Χάνουμε χρόνο διαγράφοντας ήδη διαγεγραμμένους αριθμούς.
❌ Μη αρχικοποίηση πίνακα: Όλοι οι αριθμοί πρέπει αρχικά να θεωρούνται πρώτοι.
❌ Λανθασμένος τύπος πίνακα: Στη ΓΛΩΣΣΑ χρησιμοποιούμε Λογικές: όνομα[διάσταση].

💡 10. Tips για ΑΕΠΠ & Πανελλήνιες

✍️ Απομνημόνευσε τη λογική: Ξεκίνα από 2, διαγράφεις πολλαπλάσια, πήγαινε στον επόμενο μη διαγεγραμμένο.
🔍 Οπτικοποίησε: Σχεδίασε έναν πίνακα με αριθμούς και «σβήνε» τα πολλαπλάσια.
📝 Πρόσεχε τα όρια: i*i <= N και j <= N είναι τα σωστά.
⚡ Βελτιστοποίηση: Ξεκίνα τη διαγραφή από i*i — είναι αποδεκτή και στις εξετάσεις.
🧮 Δοκίμασε με μικρά Ν: Δοκίμασε τον αλγόριθμό σου με Ν=10, Ν=30, Ν=50 για επιβεβαίωση.

❓ 11. Συχνές Ερωτήσεις (FAQ)

🔹 Μέχρι ποιο Ν μπορώ να χρησιμοποιήσω το Κόσκινο;

Θεωρητικά, όσο μεγάλο θέλουμε. Στη ΓΛΩΣΣΑ, το όριο είναι το μέγεθος του πίνακα (π.χ. 1000 ή 10000). Για μεγαλύτερα Ν, χρειαζόμαστε τμηματικό κόσκινο.

🔹 Γιατί σταματάμε στο i²;

Γιατί κάθε σύνθετος αριθμός k·i με k < i έχει ήδη διαγραφεί από κάποιον μικρότερο πρώτο. Παράδειγμα: Το 2·5=10 διαγράφηκε όταν i=2, άρα δεν χρειάζεται να το ξαναδιαγράψουμε όταν i=5.

🔹 Πόσους πρώτους έχει μέχρι το 100;

25 πρώτους: 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.

🔹 Μπορώ να βρω πρώτους με το Κόσκινο σε άλλες γλώσσες;

Ναι! Η ίδια λογική εφαρμόζεται σε Python, C, Java, JavaScript κ.λπ. Αλλάζει μόνο η σύνταξη.

🔹 Ποιος είναι ο μεγαλύτερος γνωστός πρώτος;

Ο μεγαλύτερος γνωστός πρώτος (2024) είναι ο 2^82.589.933 - 1 (περίπου 24.862.048 ψηφία). Βρέθηκε με το GIMPS, όχι με απλό κόσκινο!

🏆 12. Συμπέρασμα

Το Κόσκινο του Ερατοσθένη είναι ένας λαμπρός αλγόριθμος που συνδυάζει απλότητα, αποδοτικότητα και ιστορική αξία.

Με την υλοποίησή του σε ΓΛΩΣΣΑ (ΑΕΠΠ), μαθαίνουμε πώς να χειριζόμαστε πίνακες, επαναλήψεις και βελτιστοποιήσεις — δεξιότητες απαραίτητες για κάθε προγραμματιστή.

Εξάσκησέ τον με διαφορετικά Ν και σύντομα θα τον γράφεις αυτόματα! 💪

🎮 Δοκίμασέ το live – Διαδραστικό Demo

🔍 Κόσκινο του Ερατοσθένη interactive demo

Ο αρχαιότερος αλγόριθμος εύρεσης πρώτων αριθμών — δοκίμασέ τον ζωντανά!

📏 Όριο Ν (ακέραιος ≥ 2)

💡 Πώς λειτουργεί: Δήλωσε ένα όριο Ν και ο αλγόριθμος «κοσκινίζει» τους σύνθετους αριθμούς. Ξεκινά από τον 2, διαγράφει τα πολλαπλάσιά του, συνεχίζει με τον επόμενο μη διαγεγραμμένο. Οι αριθμοί που μένουν είναι πρώτοι. ✨ Βελτιστοποίηση: διαγραφή ξεκινά από p² και σταματάμε όταν p² > N.

🔢 Πρώτοι αριθμοί —

⚙️ Εισάγετε όριο Ν και πατήστε «Εκτέλεση»

📜 Βήματα εκτέλεσης αλγορίθμου (λογική & διαγραφές)

👆 Πατήστε "Εκτέλεση" για να δείτε live τα στάδια του κοσκίνου.

🎬 Βίντεο – Το Κόσκινο του Ερατοσθένη σε δράση

📺 Δείτε τον αλγόριθμο να εκτελείται βήμα-βήμα

📚 Διαβάστε επίσης:

🔍 Σας άρεσε το άρθρο;

Μοιραστείτε το με συμμαθητές που μαθαίνουν αλγόριθμους!

📘 Facebook 🐦 Twitter 📌 Pinterest

#Ερατοσθένης #ΚόσκινοΕρατοσθένη #ΠρώτοιΑριθμοί #ΑΕΠΠ #ΓΛΩΣΣΑ #Αλγόριθμοι #ΘεωρίαΑριθμών #Αριθμομαγεία

Δεν υπάρχουν σχόλια :

Δημοσίευση σχολίου

Εγγραφή σε: Σχόλια ανάρτησης ( Atom )

Αριθμομαγεία

LATEX

Σελίδες

Κυριακή 26 Απριλίου 2026