Ελεγκτής πρώτων αριθμών

Πρώτος αριθμός είναι ένας φυσικός αριθμός μεγαλύτερος του 1 που δεν έχει άλλους θετικούς διαιρέτες εκτός από το 1 και τον εαυτό του. Οι πρώτοι πρώτοι αριθμοί είναι οι 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Όχι, το 1 δεν θεωρείται πρώτος αριθμός. Εξ ορισμού, ένας πρώτος αριθμός πρέπει να είναι μεγαλύτερος από το 1 και να έχει ακριβώς δύο διαφορετικούς θετικούς διαιρέτες (το 1 και τον εαυτό του). Ο αριθμός 1 έχει μόνο έναν διαιρέτη.

Ναι, το 2 είναι ο μόνος ζυγός πρώτος αριθμός. Διαιρείται μόνο με το 1 και το 2. Όλοι οι άλλοι άρτιοι αριθμοί διαιρούνται με το 2, άρα δεν μπορούν να είναι πρώτοι.

Οι πρώτοι αριθμοί είναι θεμελιώδεις στα μαθηματικά και ζωτικής σημασίας για τη σύγχρονη κρυπτογραφία. Η κρυπτογράφηση RSA, που χρησιμοποιείται για την ασφάλεια των διαδικτυακών συναλλαγών, βασίζεται στη δυσκολία της παραγοντοποίησης μεγάλων αριθμών στα πρώτα τους στοιχεία.

Υπάρχουν άπειροι πρώτοι αριθμοί, όπως απέδειξε ο Ευκλείδης γύρω στο 300 π.Χ. Ανεξάρτητα από το πόσο μεγάλο πρώτο αριθμό βρίσκετε, υπάρχει πάντα ένας μεγαλύτερος. Ωστόσο, οι πρώτοι αριθμοί γίνονται όλο και πιο σπάνιοι όσο οι αριθμοί γίνονται μεγαλύτεροι - μόνο το 4% περίπου των αριθμών κοντά στο ένα εκατομμύριο είναι πρώτοι.

Από το 2024, ο μεγαλύτερος γνωστός πρώτος αριθμός είναι το 2^82,589,933 - 1, που ανακαλύφθηκε το 2018. Αυτός ο πρώτος αριθμός Μερσέν έχει 24.862.048 ψηφία. Τα νέα ρεκόρ πρώτων αριθμών ανακαλύπτονται μέσω του Great Internet Mersenne Prime Search (GIMPS), ενός κατανεμημένου υπολογιστικού έργου.

Για μικρούς αριθμούς, ελέγξτε τη διαιρετότητα με πρώτους αριθμούς μέχρι την τετραγωνική ρίζα. Για παράδειγμα, για να ελέγξετε αν το 97 είναι πρώτος αριθμός, ελέγξτε τους πρώτους αριθμούς μέχρι το √97 ≈ 9,8 (οπότε ελέγξτε τα 2, 3, 5, 7). Εφόσον το 97 δεν διαιρείται με κανένα από αυτά, είναι πρώτος αριθμός.

Οι δίδυμοι πρώτοι αριθμοί είναι ζεύγη πρώτων αριθμών που διαφέρουν κατά 2, όπως οι (3,5), (5,7), (11,13), (17,19) και (29,31). Η εικασία των δίδυμων πρώτων αριθμών υποδηλώνει ότι υπάρχουν άπειροι, αλλά αυτό παραμένει αναπόδεικτο παρά τους αιώνες μαθηματικής έρευνας.

Κάθε σύνθετος αριθμός μπορεί να εκφραστεί μοναδικά ως γινόμενο πρώτων αριθμών (Θεμελιώδες θεώρημα της αριθμητικής). Η παραγοντοποίηση πρώτων αριθμών χρησιμοποιείται στην απλοποίηση κλασμάτων, στην εύρεση GCD/LCM, στην κρυπτογραφία και στην επίλυση πολλών μαθηματικών προβλημάτων. Για παράδειγμα, 60 = 2^2 × 3 × 5.

Οι πρώτοι αριθμοί Mersenne έχουν τη μορφή 2^p - 1, όπου το p είναι επίσης πρώτος αριθμός. Παραδείγματα περιλαμβάνουν το 3 (2^2-1), το 7 (2^3-1) και το 31 (2^5-1). Είναι σημαντικοί στην εύρεση μεγάλων πρώτων αριθμών και έχουν συνδέσεις με τους τέλειους αριθμούς. Μόνο 51 πρώτοι αριθμοί Μερσέν είναι γνωστοί.