Αυτό το σεμινάριο θα σας διδάξει πώς να γράψετε ένα πρόγραμμα Python για να ελέγξετε αν ένας αριθμός είναι πρώτος ή όχι.
Εάν έχετε κάνει ποτέ τεστ κωδικοποίησης, θα έχετε συναντήσει την ερώτηση μαθηματικών στο τεστ για πρωταρχικότητα ή για να ελέγξετε αν ένας αριθμός είναι πρώτος. Και μέσα στα επόμενα λεπτά, θα μάθετε να βρίσκετε τη βέλτιστη λύση σε αυτήν την ερώτηση.
Σε αυτό το σεμινάριο, θα:
- αναθεωρήστε τα βασικά των πρώτων αριθμών,
- γράψτε τον κώδικα Python για να ελέγξετε αν ένας αριθμός είναι πρώτος και
- βελτιστοποιήστε το περαιτέρω για να λάβετε έναν αλγόριθμο χρόνου εκτέλεσης O(√n).
Για όλα αυτά και πολλά άλλα, ας ξεκινήσουμε.
Πίνακας περιεχομένων
Τι είναι ο πρώτος αριθμός;
Ας ξεκινήσουμε αναθεωρώντας τα βασικά των πρώτων αριθμών.
Στη θεωρία αριθμών, ένας φυσικός αριθμός n λέγεται ότι είναι πρωταρχικό αν έχει ακριβώς δύο παράγοντες: 1 και τον ίδιο τον αριθμό (n). Θυμηθείτε από τα μαθηματικά του σχολείου σας: ένας αριθμός i λέγεται ότι είναι παράγοντας του αριθμού n, αν διαιρεί το n ομοιόμορφα. ✅
Ο παρακάτω πίνακας παραθέτει μερικούς αριθμούς, όλους τους συντελεστές τους και αν είναι πρώτοι.
nFactorsIs Prime;11Όχι21, 2Ναι31, 3Ναι41, 2, 4Όχι71, 7Ναι151, 3, 5, 15Όχι
Από τον παραπάνω πίνακα μπορούμε να γράψουμε τα εξής:
- Το 2 είναι ο μικρότερος πρώτος αριθμός.
- Το 1 είναι συντελεστής κάθε αριθμού.
- Κάθε αριθμός n είναι ένας παράγοντας από μόνος του.
Άρα το 1 και το n είναι ασήμαντοι παράγοντες για οποιονδήποτε αριθμό n. Και ένας πρώτος αριθμός δεν πρέπει να έχει άλλους παράγοντες εκτός από αυτούς τους δύο.
Αυτό σημαίνει ότι όταν πηγαίνετε από το 2 στο n – 1, δεν θα πρέπει να μπορείτε να βρείτε έναν μη τετριμμένο παράγοντα που διαιρεί το n χωρίς υπόλοιπο.
O(n) Αλγόριθμος για να ελέγξετε εάν ένας αριθμός είναι πρώτος στην Python
Σε αυτήν την ενότητα, ας επισημοποιήσουμε την παραπάνω προσέγγιση σε μια συνάρτηση Python.
Μπορείτε να κάνετε βρόχο σε όλους τους αριθμούς από το 2 έως το n – 1 χρησιμοποιώντας το αντικείμενο range() στην Python.
Στην Python, το range(start, stop, step) επιστρέφει ένα αντικείμενο εμβέλειας. Στη συνέχεια, μπορείτε να επαναλάβετε το αντικείμενο του εύρους για να λάβετε μια ακολουθία από την αρχή μέχρι το τέλος έως τη διακοπή -1 στα βήματα του βήματος.
Εφόσον χρειαζόμαστε το σύνολο ακεραίων από το 2 έως το n-1, μπορούμε να καθορίσουμε το range(2, n) και να το χρησιμοποιήσουμε σε συνδυασμό με το βρόχο for.
Να τι θα θέλαμε να κάνουμε:
- Αν βρείτε έναν αριθμό που διαιρεί το n ομοιόμορφα χωρίς υπόλοιπο, μπορείτε να συμπεράνετε αμέσως ότι ο αριθμός δεν είναι πρώτος.
- Εάν έχετε περιηγηθεί σε ολόκληρο το εύρος των αριθμών από το 2 μέχρι το n – 1 χωρίς να βρείτε έναν αριθμό που διαιρεί ομοιόμορφα το n, τότε ο αριθμός είναι πρώτος.
Λειτουργία Python για έλεγχο του πρώτου αριθμού
Χρησιμοποιώντας τα παραπάνω, μπορούμε να προχωρήσουμε και να ορίσουμε τη συνάρτηση is_prime() ως εξής.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
Ας αναλύσουμε τώρα τον παραπάνω ορισμό συνάρτησης.
- Η παραπάνω συνάρτηση is_prime() παίρνει ως όρισμα έναν θετικό ακέραιο n.
- Εάν βρείτε έναν παράγοντα στο καθορισμένο εύρος των (2, n-1), η συνάρτηση επιστρέφει False—καθώς ο αριθμός δεν είναι πρώτος.
- Και επιστρέφει True αν διασχίσετε ολόκληρο τον βρόχο χωρίς να βρείτε παράγοντα.
Στη συνέχεια, ας καλέσουμε τη συνάρτηση με ορίσματα και ας επαληθεύσουμε εάν η έξοδος είναι σωστή.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
Στην παραπάνω έξοδο, βλέπετε ότι το 2 και το 11 είναι πρώτοι (η συνάρτηση επιστρέφει True). Και οι 8 και 9 δεν είναι πρώτοι (η συνάρτηση επιστρέφει False).
Πώς να βελτιστοποιήσετε τη συνάρτηση Python is_prime()
Μπορούμε να κάνουμε μια μικρή βελτιστοποίηση εδώ. Παρατηρήστε τη λίστα των παραγόντων στον παρακάτω πίνακα.
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Λοιπόν, μπορούμε να δούμε ότι ο μόνος παράγοντας του n που είναι μεγαλύτερος από το n/2 είναι ο ίδιος ο n.
Επομένως, αυτό σημαίνει ότι δεν χρειάζεται να κάνετε βρόχο μέχρι το n – 1. Αντίθετα, μπορείτε να εκτελέσετε τον βρόχο μόνο μέχρι το n/2.
Εάν δεν βρείτε έναν μη τετριμμένο παράγοντα μέχρι το n/2, δεν μπορείτε να βρείτε έναν επιπλέον n/2.
Τώρα ας τροποποιήσουμε τη συνάρτηση is_prime() για να ελέγξουμε για παράγοντες στο εύρος (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
Ας προχωρήσουμε και ας επαληθεύσουμε την έξοδο μέσω μερικών κλήσεων συναρτήσεων.
is_prime(9) # False is_prime(11) # True
Παρόλο που μπορεί να φαίνεται ότι έχουμε βελτιστοποιήσει, αυτός ο αλγόριθμος δεν είναι πιο αποτελεσματικός από τον προηγούμενο όσον αφορά την πολυπλοκότητα του χρόνου εκτέλεσης. Στην πραγματικότητα, και οι δύο έχουν πολυπλοκότητα χρόνου εκτέλεσης O(n): ανάλογη με την τιμή του n ή γραμμική στο n.
Μπορούμε να τα πάμε καλύτερα; Ναι μπορούμε!
▶️ Προχωρήστε στην επόμενη ενότητα για να προσδιορίσετε πώς να βελτιώσετε τη χρονική πολυπλοκότητα για τη δοκιμή πρώτων αριθμών.
O(√n) Αλγόριθμος για τον έλεγχο του πρώτου αριθμού στην Python
Συμβαίνει οι συντελεστές ενός αριθμού να εμφανίζονται σε ζεύγη.
Εάν το a είναι ένας παράγοντας του αριθμού n, τότε υπάρχει επίσης ένας παράγοντας b τέτοιος ώστε axb = n, ή απλά, ab = n.
Ας το επαληθεύσουμε αυτό μέσω ενός παραδείγματος.
Ο παρακάτω πίνακας δείχνει τους παράγοντες του αριθμού 18 που εμφανίζονται σε ζεύγη. Μπορείτε να επαληθεύσετε το ίδιο για μερικούς ακόμη αριθμούς, αν θέλετε.
Επίσης, σημειώστε ότι το √18 είναι περίπου 4,24.
Και στους παράγοντες που εμφανίζονται σε ζεύγη (a, b), μπορείτε να δείτε ότι εάν το a είναι μικρότερο από 4,24, τότε το b είναι μεγαλύτερο από 4,24 — σε αυτό το παράδειγμα, (2, 18) και (3, 6).
Παράγοντες 18 σε ζευγάρια
Το παρακάτω σχήμα δείχνει τους συντελεστές του 18 που απεικονίζονται στην αριθμητική γραμμή.
Εάν ο αριθμός n τυχαίνει να είναι τέλειο τετράγωνο, θα έχετε a = b = √n ως έναν από τους παράγοντες.
▶️ Δείτε τους συντελεστές του 36 στον παρακάτω πίνακα. Καθώς το 36 είναι τέλειο τετράγωνο, το a = b = 6 είναι ένας από τους παράγοντες. Για όλα τα άλλα ζεύγη παραγόντων (a, b), ισχύει a < 6 και b > 6.
Παράγοντες 36 ανά ζεύγη
Συνοψίζοντας, έχουμε τα εξής:
- Κάθε αριθμός n μπορεί να γραφτεί ως n = axb
- Αν το n είναι τέλειο τετράγωνο, τότε a = b = √n.
- Και αν a < b, τότε, a < √n και b > √n.
- Διαφορετικά, αν a > b, τότε a > √n και b < √n.
Έτσι, αντί να κάνετε loop σε όλους τους ακέραιους αριθμούς μέχρι το n/2, μπορείτε να επιλέξετε να τρέξετε μέχρι το √n. Και αυτό είναι πολύ πιο αποτελεσματικό από την προηγούμενη προσέγγισή μας.
Τρόπος τροποποίησης του αλγόριθμου is_prime() σε O(√n).
Ας προχωρήσουμε στη βελτιστοποίηση της συνάρτησης για έλεγχο για πρώτους αριθμούς στην Python.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n%i) == 0:
return False
return True
Τώρα, ας αναλύσουμε τον παραπάνω ορισμό συνάρτησης:
- Για να υπολογίσουμε την τετραγωνική ρίζα ενός αριθμού, ας εισαγάγουμε την ενσωματωμένη μαθηματική ενότητα της Python και ας χρησιμοποιήσουμε τη συνάρτηση math.sqrt().
- Καθώς το n μπορεί να μην είναι τέλειο τετράγωνο, θα πρέπει να το βάλουμε σε έναν ακέραιο. Χρησιμοποιήστε το int(var) για να μεταφέρετε το var σε ένα int.
- Για να βεβαιωθούμε ότι όντως ελέγχουμε μέχρι το √n, προσθέτουμε ένα συν ένα καθώς η συνάρτηση range() εξαιρεί το τελικό σημείο του εύρους από προεπιλογή.
Το κελί κώδικα παρακάτω επαληθεύει ότι η συνάρτησή μας is_prime() λειτουργεί σωστά.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
Στην επόμενη ενότητα, ας δημιουργήσουμε μερικές απλές γραφικές παραστάσεις για να κατανοήσουμε οπτικά το O(n) και το O(√n).
Σύγκριση O(n) και O(√n) Οπτικά
▶️ Εκτελέστε το παρακάτω απόσπασμα κώδικα σε ένα περιβάλλον σημειωματάριου Jupyter της επιλογής σας.
import numpy as np
import seaborn as sns
import pandas as pd
n = 20
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Το παραπάνω απόσπασμα δείχνει πώς μπορείτε να σχεδιάσετε τις καμπύλες για n και √n για μια περιοχή τιμών.
- Χρησιμοποιούμε τη συνάρτηση NumPy arange() για να δημιουργήσουμε έναν πίνακα αριθμών.
- Και μετά, συλλέγουμε τις τιμές των n και √n μέχρι, αλλά χωρίς να συμπεριλαμβάνουμε το 20, σε ένα pandas DataFrame.
- Στη συνέχεια, σχεδιάζουμε χρησιμοποιώντας seaborn’s lineplot() λειτουργία.
Από την παρακάτω γραφική παράσταση, βλέπουμε ότι το √n είναι σημαντικά μικρότερο από το n.
Ας αυξήσουμε τώρα το εύρος έως το 2000 και ας επαναλάβουμε τα ίδια βήματα όπως παραπάνω.
import numpy as np
import seaborn as sns
import pandas as pd
n = 2000
x = np.arange(n)
y1 = np.sqrt(x)
y2 = x
df = pd.DataFrame({"O(√n)":y1,"O(n)":y2})
sns.set_theme()
sns.lineplot(data = df)
Από την παραπάνω γραφική παράσταση, μπορείτε να συμπεράνετε ότι ο αλγόριθμος O(√n) είναι σημαντικά ταχύτερος όταν δοκιμάζετε εάν ένας μεγάλος αριθμός είναι πρώτος.
Ακολουθεί ένα γρήγορο παράδειγμα: Το 2377 είναι πρώτος αριθμός—επαληθεύστε αυτό!😀
Ενώ η προσέγγιση O(n) θα λάβει την τάξη των 2000 βημάτων, ο αλγόριθμος O(√n) μπορεί να σας βοηθήσει να φτάσετε στην απάντηση σε μόλις 49 βήματα.✅
συμπέρασμα
⏳ Και ήρθε η ώρα για μια γρήγορη περίληψη.
- Για να ελέγξετε εάν ένας αριθμός είναι πρώτος, η αφελής προσέγγιση είναι να κάνετε βρόχο σε όλους τους αριθμούς στο εύρος (2, n-1). Εάν δεν βρείτε έναν παράγοντα που διαιρεί το n, τότε το n είναι πρώτος.
- Καθώς ο μόνος παράγοντας n μεγαλύτερος από n/2 είναι ο ίδιος ο n, μπορείτε να επιλέξετε να τρέξετε μόνο μέχρι n/2.
- Και οι δύο παραπάνω προσεγγίσεις έχουν χρονική πολυπλοκότητα O(n).
- Καθώς οι παράγοντες ενός αριθμού εμφανίζονται σε ζεύγη, μπορείτε να τρέξετε μόνο μέχρι √n. Αυτός ο αλγόριθμος είναι πολύ πιο γρήγορος από τον O(n). Και το κέρδος είναι αισθητό όταν ελέγχετε εάν ένας μεγάλος αριθμός είναι πρώτος ή όχι.
Ελπίζω να καταλαβαίνετε πώς μπορείτε να ελέγξετε αν ένας αριθμός είναι πρώτος στην Python. Ως επόμενο βήμα, μπορείτε να δείτε το σεμινάριο μας σχετικά με τα προγράμματα Python σχετικά με τις λειτουργίες συμβολοσειρών—όπου θα μάθετε να ελέγχετε εάν οι συμβολοσειρές είναι παλίνδρομα, αναγράμματα και άλλα.
Τα λέμε όλα σε άλλο σεμινάριο. Μέχρι τότε, καλή κωδικοποίηση!👩🏽💻