Το κόσκινο του Ερατοσθένη είναι ένας αλγόριθμος για την εύρεση όλων των πρώτων αριθμών σε ένα εύρος τιμών (από 2 έως N - 1). Είναι ένας από τους αρχαιότερους γνωστούς αλγορίθμους και οφείλεται στον Έλληνα μαθηματικό και αστρονόμο Ερατοσθένη (276-194 π.Χ.). Ο αλγόριθμος εξετάζει διαδοχικά όλους τους ακεραίους και για κάθε αριθμό που συναντά διαγράφει όλα τα πολλαπλάσιά του (αφού σίγουρα δεν είναι πρώτοι).
Παρατηρήστε τα τρία πρώτα βήματα του αλγορίθμου, για N=20.
Όταν ξεκινά ο αλγόριθμος, όλοι οι αριθμοί θεωρούνται πιθανοί πρώτοι (αρχικοποιημένοι στο 1):
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ο «2» είναι πρώτος, διαγραφή των 4, 6, 8, 10, 12, 14, 16, 18, 20 (το σημειώνουμε με 0):
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Ο «3» είναι πρώτος, διαγραφή των 6, 9, 12, 15, 18:
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
Ο «4» δεν εξετάζεται γιατί έχει αφαιρεθεί σε προηγούμενο βήμα.
Ορίστε έναν πίνακα N θέσεων και αρχικοποιήστε τον με μονάδες. Η διάσταση του πίνακα να
ορίζεται μέσω #define με τιμή ίση με 50. Υλοποιήστε το κόσκινο του Ερατοσθένη σύμφωνα
με τον αλγόριθμο όπως εκφράζεται παρακάτω σε ψευδογλώσσα:
Για i=2 έως N-1 επανάλαβε
Θέσε A[i]=1
Για i=2 έως N-1 επανάλαβε
Αν A[i]!=0
Για j=2*i έως N-1 με βήμα i επανάλαβε
Θέσε A[j]=0
Για i=2 έως N-1 επανάλαβε
Αν το A[i]==1 τύπωσε "i is a prime number"
Εκτελέστε το πρόγραμμά σας και επιβεβαιώστε την ορθότητα του αποτελέσματος.
Η ψευδογλώσσα μεταφράζεται σχεδόν γραμμή προς γραμμή σε βρόχους for. Προσέξτε τα όρια:
ο πίνακας έχει θέσεις 0 έως N-1, άρα «έως N-1» σημαίνει συνθήκη < N, και ο δείκτης του
πίνακα είναι ο ίδιος ο αριθμός που εξετάζετε.
Αριθμός στον οδηγό: Α10.16
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: lab-lab06-sieve ·
Σύνδεσμος: https://progintro.github.io/study/questions/labs/lab-lab06-sieve.html ·
Markdown (GitHub)