Εισαγωγή
Αγόρασες ένα μεγάλο κουτί με διάφορα εξαρτήματα υπολογιστή σε ένα γκαράζ σέιλ.
Άρχισες να συναρμολογείς τα εξαρτήματα για να φτιάξεις υπολογιστές στα μέτρα σου.
Θέλεις να δοκιμάσεις την απόδοση διαφορετικών συνδυασμών εξαρτημάτων και αποφασίζεις να φτιάξεις το δικό σου πρόγραμμα μέτρησης επιδόσεων, για να δεις πώς συγκρίνονται οι υπολογιστές σου.
Επιλέγεις τον διάσημο αλγόριθμο "Κόσκινο του Ερατοσθένη", έναν αρχαίο αλγόριθμο, αλλά που θα πιέσει τους υπολογιστές σου στα όριά τους.
Οδηγίες
Η αποστολή σου είναι να δημιουργήσεις ένα πρόγραμμα που υλοποιεί το Κόσκινο του Ερατοσθένη, για να βρίσκει όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι με έναν δεδομένο αριθμό.
Ένας πρώτος αριθμός είναι ένας αριθμός μεγαλύτερος του 1 που διαιρείται μόνο με το 1 και τον εαυτό του.
Για παράδειγμα, οι 2, 3, 5, 7, 11 και 13 είναι πρώτοι αριθμοί.
Αντίθετα, ο 6 δεν είναι πρώτος αριθμός, καθώς δεν διαιρείται μόνο με το 1 και τον εαυτό του, αλλά και με το 2 και το 3.
Για να χρησιμοποιήσεις το Κόσκινο του Ερατοσθένη, πρώτα γράψε όλους τους αριθμούς από το 2 μέχρι και τον δεδομένο αριθμό.
Έπειτα, ακολούθησε αυτά τα βήματα:
- Βρες τον επόμενο ασημείωτο αριθμό (προσπερνώντας τους σημειωμένους).
Αυτός είναι πρώτος αριθμός.
- Σημείωσε όλα τα πολλαπλάσια αυτού του πρώτου αριθμού ως μη πρώτους.
Επανάλαβε τα βήματα μέχρι να περάσεις από όλους τους αριθμούς.
Στο τέλος, όλοι οι ασημείωτοι αριθμοί είναι πρώτοι.
Το Κόσκινο του Ερατοσθένη σημειώνει τα πολλαπλάσια κάθε πρώτου αριθμού χρησιμοποιώντας πρόσθεση (προσθέτοντας επανειλημμένα τον πρώτο) ή πολλαπλασιασμό (υπολογίζοντας απευθείας τα πολλαπλάσιά του), αντί να ελέγχει κάθε αριθμό για το αν διαιρείται.
Τα tests δεν ελέγχουν αν έχεις υλοποιήσει τον αλγόριθμο, μόνο αν έχεις βρει τους σωστούς πρώτους αριθμούς.
Παράδειγμα
Ας υποθέσουμε ότι βρίσκεις τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι με το 10.
-
Γράψε τους 2, 3, 4, 5, 6, 7, 8, 9, 10, αφήνοντάς τους όλους ασημείωτους.
2 3 4 5 6 7 8 9 10
-
Το 2 είναι ασημείωτο και επομένως είναι πρώτος.
Σημείωσε τα 4, 6, 8 και 10 ως "μη πρώτους".
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
Το 3 είναι ασημείωτο και επομένως είναι πρώτος.
Σημείωσε τα 6 και 9 ως μη πρώτους (το να σημειώσεις το 6 είναι προαιρετικό, αφού έχει ήδη σημειωθεί).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 4 είναι σημειωμένο ως "μη πρώτος", οπότε το προσπερνάμε.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 5 είναι ασημείωτο και επομένως είναι πρώτος.
Σημείωσε το 10 ως μη πρώτο (προαιρετικό, αφού έχει ήδη σημειωθεί).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 6 είναι σημειωμένο ως "μη πρώτος", οπότε το προσπερνάμε.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 7 είναι ασημείωτο και επομένως είναι πρώτος.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 8 είναι σημειωμένο ως "μη πρώτος", οπότε το προσπερνάμε.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 9 είναι σημειωμένο ως "μη πρώτος", οπότε το προσπερνάμε.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
Το 10 είναι σημειωμένο ως "μη πρώτος", οπότε σταματάμε, αφού δεν υπάρχουν άλλοι αριθμοί για έλεγχο.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Έχεις εξετάσει όλους τους αριθμούς και βρήκες ότι οι 2, 3, 5 και 7 παραμένουν ασημείωτοι, δηλαδή είναι οι πρώτοι αριθμοί που είναι μικρότεροι ή ίσοι με το 10.
