Πώς μπορούμε να ελέγξουμε αν ένας αριθμός είναι πρώτος;

 

📚Αν θέλεις να θυμηθείς πότε ένας αριθμός λέγεται πρώτος, μπορείς να το διαβάσεις εδώ...

 

Image credit: Michael Jay Berlin via Shutterstock

Πολλές φορές, χρειάζεται να ελέγξουμε αν ένας αριθμός n είναι πρώτος. Μια βασική διαδικασία είναι η δοκιμαστική διαίρεση, δηλαδή να ελέγξουμε αν ο αριθμός n είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το \(\sqrt{n}\). Απαραίτητα εδώ είναι τα κριτήρια διαιρετότητας.

 

Παραδείγματα:

✅Θέλουμε να εξετάσουμε αν ο αριθμός 169 είναι πρώτος. Αρκεί να ελέγξουμε αν το 169 είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το \(\sqrt{169}=13\).

Το 2 δεν διαιρεί το 169.

Το 3 δεν διαιρεί το 169.

Ομοίως, το 4, το 5, το 6, το 7, το 8, το 9, το 10, το 11 και το 12 δεν διαιρούν το 169.

Το 13 διαιρεί το 169.

Άρα το 169 δεν είναι πρώτος αριθμός.

 

✅Θέλουμε να εξετάσουμε αν ο αριθμός 51 είναι πρώτος. Επειδή 49<51 δηλαδή \(7<\sqrt{51}\),  αρκεί να ελέγξουμε αν το 51 είναι πολλαπλάσιο κάποιου αριθμού από το 2  έως και το 7.

Το 2 δεν διαιρεί το 51.

Το 3 διαιρεί το 51.

Άρα το 51 δεν είναι πρώτος αριθμός.

 

✅Θέλουμε να εξετάσουμε αν ο αριθμός 113 είναι πρώτος. Επειδή 100<113 δηλαδή \(10<\sqrt{113}\),  αρκεί να ελέγξουμε αν το 113 είναι πολλαπλάσιο κάποιου αριθμού από το 2 έως και το 10.

Βρίσκουμε ότι κανένας από τους αριθμούς 2, 3, 4, 5, 6, 7, 8, 9, 10 δεν διαιρεί το 113.

Άρα το 113 είναι πρώτος αριθμός.

 

💡Η μέθοδος της δοκιμαστικής διαίρεσης μπορεί να εφαρμοστεί πιο αποτελεσματικά αν είναι γνωστοί όλοι οι πρώτοι αριθμοί μέχρι και το \(\sqrt{n}\). Για παράδειγμα, για να ελέγξουμε αν ο 113 είναι πρώτος, αρκεί να ελέγξουμε αν διαιρείται μόνο από το 2, το 3, το 5 και το 7.

 

🚩Για πολύ μεγάλους αριθμούς, η μέθοδος αυτή γίνεται πολύ αργή και μη πρακτική, γιατί το πλήθος των πιθανών παραγόντων του n αυξάνεται ραγδαία καθώς αυξάνεται ο n. Για την ακρίβεια, το πλήθος των πρώτων αριθμών μικρότερων του \(\sqrt{n}\) είναι της τάξης \(\frac{\sqrt{n}}{ln(\sqrt{n})}\).  Για τον έλεγχο πολύ μεγάλων αριθμών, έχουν αναπτυχθεί διάφοροι αλγόριθμοι που τρέχουν σε υπολογιστικά συστήματα.

🔍Διάβασε εδώ περισσότερα γύρω από τους πρώτους αριθμούς.