Έλεγχος πρώτων αριθμών

Πώς να χρησιμοποιήσετε τον έλεγχο πρώτων αριθμών

1. Πληκτρολογήστε έναν Ακέραιο αριθμό. Γίνονται δεκτές και παραστάσεις: 2^61-1, 10^12+39, 20!+1 ή 3711.
2. Η απάντηση εμφανίζεται καθώς πληκτρολογείτε· πατήστε Έλεγχος για να δώσετε περισσότερο χρόνο στην ανάλυση ενός δύσκολου αριθμού.
3. Διαβάστε το συμπέρασμα, την Ανάλυση σε πρώτους παράγοντες, το Πλήθος διαιρετών, τον Προηγούμενο πρώτο και τον Επόμενο πρώτο. Το πλαίσιο Γιατί εξηγεί πώς προέκυψε η απάντηση και η Αντιγραφή ανάλυσης αντιγράφει το γινόμενο των πρώτων.
4. Για να δείτε μια λίστα πρώτων, συμπληρώστε τα Από και Έως στην ενότητα Πρώτοι αριθμοί σε διάστημα και πατήστε Εμφάνιση πρώτων.

Γίνονται δεκτοί αριθμοί έως 2048 bit (περίπου 617 ψηφία) και όλα εκτελούνται στο πρόγραμμα περιήγησής σας. Τίποτα από όσα πληκτρολογείτε δεν στέλνεται σε διακομιστή.

Τι κάνει έναν αριθμό πρώτο

Πρώτος αριθμός είναι ένας ακέραιος μεγαλύτερος του 1 που έχει ως μοναδικούς διαιρέτες το 1 και τον εαυτό του: 2, 3, 5, 7, 11, 13… Ένας αριθμός με άλλους διαιρέτες λέγεται σύνθετος και γράφεται με έναν και μοναδικό τρόπο ως γινόμενο πρώτων, δηλαδή με την ανάλυσή του σε πρώτους παράγοντες (360 = 2³ × 3² × 5). Το 0 και το 1 δεν είναι ούτε πρώτοι ούτε σύνθετοι και το 2 είναι ο μόνος άρτιος πρώτος.

Το πλήθος των διαιρετών προκύπτει από την ανάλυση: προσθέτετε 1 σε κάθε εκθέτη και πολλαπλασιάζετε. Το 360 = 2³ × 3² × 5 έχει (3 + 1)(2 + 1)(1 + 1) = 24 διαιρέτες. Ένας πρώτος έχει πάντα ακριβώς 2.

Πώς λειτουργεί ο έλεγχος

• Οι μικροί αριθμοί (κάτω από ένα εκατομμύριο) ελέγχονται με δοκιμαστική διαίρεση: αν κανένας πρώτος έως την τετραγωνική ρίζα δεν διαιρεί τον αριθμό, ο αριθμός είναι πρώτος. Δεν χρειάζεται να προχωρήσετε παραπέρα, γιατί ένας σύνθετος αριθμός έχει πάντα παράγοντα όχι μεγαλύτερο από την τετραγωνική του ρίζα.
• Οι μεγαλύτεροι αριθμοί διαιρούνται πρώτα με κάθε πρώτο κάτω από το 1000 και έπειτα υποβάλλονται στον έλεγχο Miller–Rabin. Με τις 13 βάσεις 2, 3, 5, …, 41 ο έλεγχος αυτός έχει αποδειχθεί ακριβής για κάθε αριθμό κάτω από 3,3 × 10²⁴, δηλαδή για όλους τους ακέραιους των 64 bit. Για αυτούς τους αριθμούς η απάντηση είναι βέβαιη.
• Πάνω από 3,3 × 10²⁴ χρησιμοποιούνται 25 βάσεις και ένας αριθμός που τις περνά όλες αναφέρεται ως πιθανώς πρώτος. Η πιθανότητα λάθους είναι μικρότερη από 1 στα 10¹⁵, αλλά δεν αποτελεί μαθηματική απόδειξη. Όταν ο έλεγχος αποτυγχάνει, ο αριθμός είναι σίγουρα σύνθετος.

Πώς αναλύονται οι αριθμοί σε παράγοντες

Οι μικροί παράγοντες βρίσκονται με δοκιμαστική διαίρεση. Τα μεγαλύτερα σύνθετα τμήματα διασπώνται με τον αλγόριθμο rho του Pollard (παραλλαγή του Brent), ο οποίος βρίσκει παράγοντες έως περίπου 10 ψηφίων σε κλάσμα του δευτερολέπτου. Οι δυσκολότεροι αριθμοί, όπως το γινόμενο δύο πρώτων των 15 ψηφίων ή περισσότερων, μπορεί να χρειάζονται πολύ περισσότερο από οποιοδήποτε χρονικό όριο, γι’ αυτό η ανάλυση σταματά μετά από λίγα δευτερόλεπτα. Ο τελευταίος παράγοντας σημειώνεται τότε ως σύνθετος αλλά μη αναλυμένος και, αν πατήσετε ξανά Έλεγχος, του δίνεται περισσότερος χρόνος.

Πρώτοι αριθμοί σε διάστημα

Η λίστα του διαστήματος χρησιμοποιεί κοσκίνισμα του Ερατοσθένη σε τμήματα, το οποίο διαγράφει τα πολλαπλάσια κάθε πρώτου. Δέχεται έως 1.000.000 αριθμούς ανά διάστημα, με άνω όριο έως 10¹². Το πλήθος αφορά ολόκληρο το διάστημα, ενώ εμφανίζονται οι πρώτοι 2.000 πρώτοι αριθμοί. Για παράδειγμα, υπάρχουν 25 πρώτοι ανάμεσα στο 1 και στο 100 και 78.498 κάτω από το ένα εκατομμύριο.