Αριθμητικοί αλγόριθμοι

Διαιρέτες και πρώτοι αριθμοί

Δοκιμαστικές διαιρέσεις

Ένας ακέραιος $n \geq 2$ είναι πρώτος αν οι μόνοι θετικοί διαιρέτες του είναι το 1 και ο $n$· αν έχει κι άλλον, είναι σύνθετος· το 0 και το 1 δεν είναι ούτε το ένα ούτε το άλλο. Ο ορισμός υποδεικνύει αμέσως έναν αλγόριθμο: να δοκιμάσουμε κάθε υποψήφιο $d$ από το 2 έως το $n - 1$ και να κηρύξουμε τον αριθμό σύνθετο μόλις κάποιος τον διαιρέσει. Είναι ο βρόχος του μικρότερου διαιρέτη από το μάθημα Βρόχοι, και είναι σωστός. Ωστόσο, για έναν πρώτο με δέκα ψηφία κάνει σχεδόν δέκα δισεκατομμύρια διαιρέσεις, και σχεδόν όλες είναι άχρηστες, για τον εξής λόγο.

Από αυτό έπεται ότι το πλήθος των διαιρέσεων πέφτει από περίπου $n$ σε περίπου $\sqrt{n}$: για $n$ κοντά στα δύο δισεκατομμύρια, από δύο δισεκατομμύρια σε σαράντα έξι χιλιάδες. Το πρόγραμμα χρησιμοποιεί το μοτίβο της σημαίας από το μάθημα Σχεδίαση σωστών βρόχων: η isPrime ξεκινά αληθής και ο βρόχος τη σβήνει αν βρει διαιρέτη.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d <= n / d; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    if (isPrime) {        std::println("Ο {} είναι πρώτος", n);    } else {        std::println("Ο {} δεν είναι πρώτος", n);    }}

2147483647

Ο 2147483647 είναι πρώτος

Τρεις αποφάσεις αξίζουν σχόλιο. Η σημαία αρχικοποιείται με n >= 2, ώστε το 0, το 1 και οι αρνητικοί να κηρύσσονται μη πρώτοι χωρίς να μπουν στον βρόχο: η παράλειψη αυτής της περίπτωσης είναι το τυπικό σφάλμα, γιατί με $n = 1$ ο βρόχος δεν κάνει κανέναν γύρο και το πρόγραμμα θα κήρυσσε πρώτο το 1. Η συνθήκη του for έχει δύο μέρη: τη σημαία, που σταματά τον βρόχο στον πρώτο διαιρέτη, και το όριο. Και το όριο γράφεται d <= n / d, που, για θετικούς ακεραίους, ισοδυναμεί με $d^2 \leq n$ (η ακέραια διαίρεση αποκόπτει, αλλά ο $d$ δεν υπερβαίνει το αποκομμένο πηλίκο ακριβώς όταν δεν υπερβαίνει το $n/d$, επειδή ο $d$ είναι ακέραιος). Ο αριθμός της εισόδου, ο $2^{31} - 1$, είναι ο μεγαλύτερος int και είναι πρώτος· το πρόγραμμα το αποφασίζει με $46\,339$ υπόλοιπα, εκείνα των υποψηφίων από το 2 έως το $46\,340$.

Η αναλλοίωτη του βρόχου είναι: κανένας ακέραιος από το 2 έως το $d - 1$ δεν διαιρεί τον $n$, όσο η σημαία μένει αληθής. Ισχύει κατά την είσοδο, όταν το διάστημα από το 2 έως το 1 είναι κενό· διατηρείται, γιατί αν ο $d$ δεν διαιρεί τον $n$ το διάστημα μεγαλώνει κατά έναν αριθμό που δεν διαιρεί· και κατά την έξοδο με τη σημαία αληθή, η αναλλοίωτη και η ψευδής συνθήκη, $d^2 > n$, λένε μαζί ότι κανένας υποψήφιος έως το $\sqrt{n}$ δεν διαιρεί τον $n$, που είναι ό,τι απαιτεί η πρόταση. Η φθίνουσα ποσότητα είναι το πλήθος των υποψηφίων που μένουν να δοκιμαστούν, δηλαδή των ακεραίων μεταξύ $d$ και $\sqrt{n}$: μειώνεται κατά ένα σε κάθε γύρο και δεν πέφτει κάτω από το μηδέν.

Η συνθήκη που υπερχειλίζει

Ο φυσικός τρόπος να γραφτεί το όριο είναι d * d <= n, και είναι λάθος. Με την ίδια είσοδο, ο βρόχος φτάνει στο $d = 46\,341$, και τότε το γινόμενο $46\,341^2 = 2\,147\,488\,281$ υπερβαίνει το μέγιστο του int.

#include <iostream>#include <print>​int main(){    int n{};    std::cin >> n;    bool isPrime{n >= 2};    for (int d{2}; isPrime && d * d <= n; ++d) {        if (n % d == 0) {            isPrime = false;        }    }    std::println("Πρώτος; {}", isPrime);}

2147483647

main.cpp:9:33: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int'

Ο ανιχνευτής απροσδιόριστης συμπεριφοράς σταματά το πρόγραμμα στο γινόμενο. Χωρίς αυτόν, η υπερχείλιση με πρόσημο είναι απροσδιόριστη συμπεριφορά, και το πρότυπο δεν λέει τι συμβαίνει. Αυτό που παρατηρείται με τον GCC σε Linux, με και χωρίς βελτιστοποίηση, είναι διδακτικό: το γινόμενο κάνει αναδίπλωση και γίνεται αρνητικό ή μικρότερο από τον $n$, και, αφού κανένας int δεν υπερβαίνει το μέγιστο, η συνθήκη d * d <= n δεν παύει πια να ισχύει· ο βρόχος συνεχίζει να δοκιμάζει υποψηφίους για περίπου δύο δισεκατομμύρια γύρους, ώσπου να φτάσει στο $d = n$, που διαιρεί τον $n$, και το πρόγραμμα κηρύσσει σύνθετο έναν πρώτο αριθμό. Ένα σφάλμα υπερχείλισης δεν εκδηλώνεται ως υπερχείλιση, αλλά ως λανθασμένη απάντηση. Η μορφή d <= n / d δεν μπορεί να υπερχειλίσει, γιατί διαιρεί αντί να πολλαπλασιάζει· το μάθημα Bit και μαθηματική βιβλιοθήκη πρόσφερε άλλη διέξοδο, τον υπολογισμό του ορίου μία φορά με τη std::sqrt, αλλά τότε η ακρίβεια του ορίου εξαρτάται από τη στρογγυλοποίηση της κινητής υποδιαστολής, ενώ η ακέραια διαίρεση δεν έχει αυτό το πρόβλημα.

Το μάθημα «Πρώτοι αριθμοί και το θεμελιώδες θεώρημα της αριθμητικής», του κύκλου μαθημάτων Άλγεβρα και γεωμετρία I, αποδεικνύει ότι κάθε ακέραιος μεγαλύτερος από 1 είναι γινόμενο πρώτων με έναν μόνο τρόπο· οι δοκιμαστικές διαιρέσεις είναι ο πιο άμεσος τρόπος να βρεθεί αυτό το γινόμενο, διαιρώντας τον $n$ με κάθε διαιρέτη που βρίσκεται και συνεχίζοντας με το πηλίκο.