Εισαγωγή
Αγόρασες ένα μεγάλο κουτί με διάφορα εξαρτήματα υπολογιστή σε ένα γκαράζ σέιλ.
Άρχισες να συναρμολογείς τα εξαρτήματα για να φτιάξεις υπολογιστές στα μέτρα σου.
Θέλεις να δοκιμάσεις την απόδοση διαφορετικών συνδυασμών εξαρτημάτων και αποφασίζεις να φτιάξεις το δικό σου πρόγραμμα μέτρησης επιδόσεων, για να δεις πώς συγκρίνονται οι υπολογιστές σου.
Επιλέγεις τον διάσημο αλγόριθμο "Κόσκινο του Ερατοσθένη", έναν αρχαίο αλγόριθμο, αλλά που θα πιέσει τους υπολογιστές σου στα όριά τους.
Οδηγίες
Η αποστολή σου είναι να δημιουργήσεις ένα πρόγραμμα που υλοποιεί τον αλγόριθμο του Κόσκινου του Ερατοσθένη για να βρεις όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι με έναν δεδομένο αριθμό.
Ένας πρώτος αριθμός είναι ένας αριθμός μεγαλύτερος του 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 δεν έχει σημειωθεί και επομένως είναι πρώτος.
Σήμανε τους 4, 6, 8 και 10 ως "μη πρώτους".
- Ο 3 δεν έχει σημειωθεί και επομένως είναι πρώτος.
Σήμανε τους 6 και 9 ως μη πρώτους (η σήμανση του 6 είναι προαιρετική - έχει ήδη σημειωθεί).
- Ο 4 έχει σημειωθεί ως "μη πρώτος", οπότε τον προσπερνάμε.
- Ο 5 δεν έχει σημειωθεί και επομένως είναι πρώτος.
Σήμανε τον 10 ως μη πρώτο (προαιρετικό - έχει ήδη σημειωθεί).
- Ο 6 έχει σημειωθεί ως "μη πρώτος", οπότε τον προσπερνάμε.
- Ο 7 δεν έχει σημειωθεί και επομένως είναι πρώτος.
- Ο 8 έχει σημειωθεί ως "μη πρώτος", οπότε τον προσπερνάμε.
- Ο 9 έχει σημειωθεί ως "μη πρώτος", οπότε τον προσπερνάμε.
- Ο 10 έχει σημειωθεί ως "μη πρώτος", οπότε σταματάμε καθώς δεν υπάρχουν άλλοι αριθμοί για έλεγχο.
Έχεις εξετάσει όλους τους αριθμούς και βρήκες ότι οι 2, 3, 5 και 7 παραμένουν χωρίς σημείωση, που σημαίνει ότι είναι οι πρώτοι αριθμοί που είναι μικρότεροι ή ίσοι με το 10.
