Μάθετε πρώτα τον ορισμό
Πρώτος αριθμός είναι ένας ακέραιος αριθμός μεγαλύτερος από το 1 με ακριβώς δύο θετικούς διαιρέτες: το 1 και τον ίδιο τον αριθμό. Οι πρώτοι πρώτοι είναι οι 2, 3, 5, 7, 11 και 13. Ο αριθμός 1 δεν είναι ούτε πρώτος ούτε σύνθετος και το 2 είναι ο μόνος άρτιος πρώτος.
Ελέγξτε μόνο μέχρι την τετραγωνική ρίζα
Για να ελέγξετε έναν θετικό ακέραιο n, δεν χρειάζεται να δοκιμάσετε κάθε αριθμό κάτω από το n. Αν το n έχει παράγοντα μεγαλύτερο από την τετραγωνική του ρίζα, πρέπει επίσης να έχει συντελεστή αντιστοίχισης μικρότερο από την τετραγωνική ρίζα. Αρκεί λοιπόν να δοκιμάσουμε πιθανούς διαιρέτες μέχρι την τετραγωνική ρίζα.
- Αν ο αριθμός είναι μικρότερος από 2, δεν είναι πρώτος.
- Ελέγξτε αν διαιρείται με το 2. Αν είναι άρτιος και μεγαλύτερος του 2, δεν είναι πρώτος.
- Δοκιμάστε περιττούς διαιρέτες από το 3 μέχρι την τετραγωνική ρίζα. Αν κάποιο διαιρείται ομοιόμορφα, ο αριθμός είναι σύνθετος.
- Αν κανένα δεν διαιρείται ομοιόμορφα, ο αριθμός είναι πρώτος.
Παράδειγμα: το 97 είναι πρώτος;
Η τετραγωνική ρίζα του 97 είναι λίγο μικρότερη από το 10. Ελέγξτε τους πιθανούς πρώτους διαιρέτες μέχρι εκείνο το σημείο: 2, 3, 5 και 7. Ο αριθμός δεν διαιρείται με κανέναν από αυτούς, άρα το 97 είναι πρώτος.
Για το 91, ο έλεγχος βρίσκει 7: 91 ÷ 7 = 13. Αυτό είναι αρκετό για να δείξει ότι το 91 είναι σύνθετο. δεν χρειάζεται να δοκιμάσετε μεγαλύτερους διαιρέτες.
Συνήθη λάθη
- Κλήση 1 prime. Ένας πρώτος πρέπει να έχει ακριβώς δύο θετικούς διαιρέτες, ενώ ο 1 έχει μόνο έναν.
- Υποθέτοντας ότι κάθε περιττός αριθμός είναι πρώτος. Τα περιττά σύνθετα όπως το 9, 15, 21 και 91 έχουν περιττούς διαιρέτες.
- Δοκιμάζοντας μόνο μερικούς μικρούς διαιρέτες για μεγάλο αριθμό. Ο έλεγχος πρέπει να καλύπτει κάθε πιθανό διαιρέτη μέχρι την τετραγωνική ρίζα ή να χρησιμοποιεί έναν επαληθευμένο αλγόριθμο πρωταρχικότητας.
Το UsefulVerse ελέγχει τις πρακτικές εισαγωγές ακέραιου αριθμού τοπικά στο πρόγραμμα περιήγησής σας. Ένα πρωταρχικό αποτέλεσμα είναι ένας έλεγχος διαιρετότητας, όχι μια απόδειξη για ένα κρυπτογραφικό κλειδί ή ένα υποκατάστατο για εξειδικευμένο λογισμικό θεωρίας αριθμών.