Πρώτοι αριθμοί

Τελευταία ενημέρωση: 4/10/2016, 21:44

Πρόβλημα 1

Ένας φυσικός αριθμός είναι πρώτος αν και μόνο αν το σύνολο των διαιρετών του έχει πλήθος στοιχείων ίσο με 2.

Γράψτε μία συνάρτηση με μία ακέραια παράμετρο η οποία επιστρέφει έναν λογικό τύπο ο οποίος ισούται με Αληθής αν η παράμετρος είναι πρώτος αριθμός και με Ψευδής αν δεν είναι πρώτος.

Λύση

pr

Απόδειξη ορθότητας

Με βάση τον ορισμό του πρώτου αριθμού που δίνεται στην διατύπωση του προβλήματος το 0 και το 1 δεν είναι πρώτοι αριθμοί, γιατί το πλήθος των διαιρετών του 0 ({1,2,3,4,…}) είναι άπειρο, ενώ το πλήθος των διαιρετών του 1 ({1}) είναι 1. Κάθε φυσικός αριθμός μεγαλύτερος του 1 έχει σύνολο διαιρετών με πλήθος τουλάχιστον 2. Πράγματι, κάθε φυσικός αριθμός μεγαλύτερος του 1 διαιρείται με τον εαυτό του και το 1. Επομένως, για να είναι πρώτος ένας φυσικός αριθμός μεγαλύτερος του 1 θα πρέπει να μην έχει κανένα άλλο διαιρέτη εκτός από αυτούς που προαναφέραμε. Με βάση τα προηγούμενα η απόδειξη ορθότητας του αλγορίθμου είναι άμεση.

Σχόλια

-Ελέγχουμε αν ο φυσικός αριθμός k διαιρείται με τον φυσικό αριθμό m χρησιμοποιώντας τον τελεστή MOD: αν k MOD m = 0, ο m είναι διαιρέτης του k και αντίστροφα (αυτός είναι και ο τυπικός μαθηματικός ορισμός).

-Στο παραπάνω πρόγραμμα η επαναληπτική δομή ΓΙΑ δεν εκτελείται για κ = 2, αφού η αρχική τιμή που θα πάρει η μεταβλητή-μετρητής ι είναι 2-1 = 1: ο έλεγχος της συνθήκης 1 >= 2 (η οποία είναι ψευδής) που ακολουθεί (ο τελεστής >= είναι λόγω του αρνητικού βήματος) δεν επιτρέπει την εκτέλεση καμιάς επανάληψης.

Πρόβλημα 2
Ένας φυσικός αριθμός μεγαλύτερος του 1 ο οποίος δεν είναι πρώτος λέγεται “σύνθετος”.

Λύστε το πρόβλημα 1 χρησιμοποιώντας τα παρακάτω δύο θεωρήματα:

1) Ένας φυσικός αριθμός μεγαλύτερος του 1 ο οποίος είναι σύνθετος γράφεται ως γινόμενο πρώτων παραγόντων, με πλήθος παραγόντων τουλάχιστον 2 – και μάλιστα κατά μοναδικό τρόπο, αν θεωρήσουμε ότι τα γινόμενα που προκύπτουν με την εφαρμογή της αντιμεταθετικής ιδιότητας του πολλαπλασιασμού δεν συνιστούν διαφορετικό γινόμενο. Για παράδειγμα ο αριθμός 4 γράφεται μοναδικά ως γινόμενο πρώτων παραγόντων ως 2⋅2. Το θεώρημα είναι γνωστό και ως “θεμελιώδες θεώρημα της αριθμητικής” *.

2) Εάν ένας αριθμός είναι πρώτος μεγαλύτερος του 3, τότε ο επόμενος ή ο προηγούμενος είναι πολλαπλάσιο του 6” (το αντίστροφο δεν ισχύει).

Λύση

pr2

Απόδειξη ορθότητας

Ένας πρώτος αριθμός σίγουρα δεν γράφεται ως γινόμενο με τουλάχιστον δύο πρώτους παράγοντες, αφού οι μόνοι του διαιρέτες είναι το 1 και ο εαυτός του: γράφεται μόνο ως γινόμενο του εαυτού του με το 1, και το 1 δεν είναι πρώτος αριθμός. Από το δεύτερο θεώρημα συνεπάγεται ότι μπορούμε να αναζητήσουμε τους πρώτους αριθμούς που είναι μεγαλύτεροι του 3 δίπλα (πριν ή μετά) από τα πολλαπλάσια του 6. Από το ίδιο θεώρημα συνεπάγεται επίσης (μέσω αντιθετοαντιστροφής) ότι “αν για έναν αριθμό μεγαλύτερο του 3 ισχύει ότι ούτε ο προηγούμενος ούτε ο επόμενος είναι πολλαπλάσιο του 6, τότε ο αριθμός είναι σύνθετος”. Από το πρώτο θεώρημα και τον ορισμό του πρώτου και του σύνθετου αριθμού συνεπάγεται ότι προκειμένου να αποδείξουμε ότι ένας αριθμός μεγαλύτερος του 1 είναι πρώτος αρκεί να εξετάσουμε αν υπάρχει πρώτος διαιρέτης του, ο οποίος βέβαια πρέπει να είναι διαφορετικός από τον ίδιο τον αριθμό (αν υπάρχει ο αριθμός δεν είναι πρώτος, αλλιώς είναι). Από τα παραπάνω συνεπάγεται άμεσα η ορθότητα του προγράμματος.

Σχόλια

Ο τελεστής MOD έχει την ίδια προτεραιότητα με τον τελεστή του πολλαπλασιασμού (*) και της διαίρεσης (/), η οποία είναι μεγαλύτερη από αυτή του τελεστή πρόσθεσης (+) και αφαίρεσης (-). Οπότε, για παράδειγμα, αν θέλουμε να ελέγξουμε αν ένας αριθμός κ δεν διαιρείται με τον προηγούμενο ενός αριθμού ι, χρησιμοποιούμε την συνθήκη κ MOD (ι-1) <> 0, περικλείοντας με παρενθέσεις το “ι-1”. Σε διαφορετική περίπτωση θα εκτελεστεί (κ MOD ι) – 1 , το οποίο είναι διαφορετικό.

Άσκηση για εμβάθυνση

Λύστε το πρόβλημα 1 χρησιμοποιώντας επιπλέον το παρακάτω θεώρημα:

Εάν ένας αριθμός είναι σύνθετος, τότε υπάρχει ένας πρώτος διαιρέτης του ο οποίος είναι μικρότερος ή ίσος από την τετραγωνική ρίζα του αριθμού (η τετραγωνική ρίζα ενός φυσικού αριθμού είναι γενικά πραγματικός αριθμός).

*Πάραυτα δεν διδάσκεται στην πρωτοβάθμια, ούτε στην δευτεροβάθμια εκπαίδευση