Denne opplæringen vil lære deg hvordan du skriver et Python-program for å sjekke om et tall er primtall eller ikke.
Hvis du noen gang har tatt opp kodeprøver, vil du ha kommet over mattespørsmålet på testen for primalitet eller for å sjekke om et tall er primtall. Og i løpet av de neste minuttene vil du lære å finne den optimale løsningen på dette spørsmålet.
I denne opplæringen skal du:
- gjennomgå det grunnleggende om primtall,
- skriv Python-kode for å sjekke om et tall er primtall, og
- optimalisere den ytterligere for å få en O(√n) kjøretidsalgoritme.
For alt dette og mer, la oss komme i gang.
Innholdsfortegnelse
Hva er et primtall?
La oss starte med å gjennomgå det grunnleggende om primtall.
I tallteori sies et naturlig tall n å være prime hvis den har nøyaktig to faktorer: 1 og selve tallet (n). Husk fra skolens matematikk: et tall i sies å være en faktor av tallet n, hvis i deler n jevnt. ✅
Tabellen nedenfor viser noen få tall, alle faktorene deres, og om de er primtall.
nFactorsIs Prime?11Nei21, 2Ja31, 3Ja41, 2, 4Nei71, 7Ja151, 3, 5, 15Nei
Fra tabellen ovenfor kan vi skrive ned følgende:
- 2 er det minste primtallet.
- 1 er en faktor for hvert tall.
- Hvert tall n er en faktor i seg selv.
Så 1 og n er trivielle faktorer for et hvilket som helst tall n. Og et primtall skal ikke ha andre faktorer enn disse to.
Dette betyr at når du går fra 2 til n – 1, skal du ikke kunne finne en ikke-triviell faktor som deler n uten en rest.
O(n) Algoritme for å sjekke om et tall er primtall i Python
I denne delen, la oss formalisere tilnærmingen ovenfor til en Python-funksjon.
Du kan gå gjennom alle tall fra 2 til n – 1 ved å bruke range()-objektet i Python.
I Python returnerer range(start, stop, step) et områdeobjekt. Du kan deretter iterere over rekkeviddeobjektet for å få en sekvens fra start og helt opp til stopp -1 i trinnvis.
Siden vi trenger settet med heltall fra 2 til n-1, kan vi spesifisere range(2, n) og bruke det sammen med for loop.
Her er hva vi ønsker å gjøre:
- Hvis du finner et tall som deler n jevnt uten en rest, kan du umiddelbart konkludere med at tallet ikke er primtall.
- Hvis du har gått gjennom hele rekkevidden av tall fra 2 helt opp til n – 1 uten å finne et tall som deler n jevnt, så er tallet primtall.
Python-funksjon for å se etter primtall
Ved å bruke ovenstående kan vi gå videre og definere funksjonen is_prime() som følger.
def is_prime(n):
for i in range(2,n):
if (n%i) == 0:
return False
return True
La oss nå analysere funksjonsdefinisjonen ovenfor.
- Funksjonen ovenfor is_prime() tar inn et positivt heltall n som argument.
- Hvis du finner en faktor i det spesifiserte området (2, n-1), returnerer funksjonen False – siden tallet ikke er primtall.
- Og den returnerer True hvis du krysser hele loopen uten å finne en faktor.
La oss deretter kalle funksjonen med argumenter og verifisere om utgangen er riktig.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True
I utgangen ovenfor ser du at 2 og 11 er prime (funksjonen returnerer True). Og 8 og 9 er ikke primtall (funksjonen returnerer False).
Hvordan optimalisere Python-funksjonen is_prime()
Vi kan gjøre en liten optimalisering her. Se på listen over faktorer i tabellen nedenfor.
NumberFactors61, 2, 3, 6101, 2, 5, 10181, 2, 3, 6, 9, 18
Vel, vi kan se at den eneste faktoren til n som er større enn n/2 er n selv.
Så dette betyr at du ikke trenger å gå helt opp til n – 1. Du kan i stedet kjøre loopen bare opp til n/2.
Hvis du ikke finner en ikke-triviell faktor før n/2, kan du heller ikke finne en utover n/2.
La oss nå endre funksjonen is_prime() for å se etter faktorer i området (2, n/2)
def is_prime(n):
for i in range(2,int(n/2)):
if (n%i) == 0:
return False
return True
La oss gå videre og verifisere utdataene gjennom noen funksjonskall.
is_prime(9) # False is_prime(11) # True
Selv om det kan virke som vi har optimalisert, er ikke denne algoritmen mer effektiv enn den forrige når det gjelder kjøretidskompleksitet. Faktisk har begge O(n) kjøretidskompleksitet: proporsjonal med verdien av n eller lineær i n.
Kan vi gjøre det bedre? Ja vi kan!
▶️ Fortsett til neste avsnitt for å finne ut hvordan du kan forbedre tidskompleksiteten for primtallstesting.
O(√n) Algoritme for å se etter primtall i Python
Det hender at faktorene til et tall forekommer i par.
Hvis a er en faktor av tallet n, så eksisterer det også en faktor b slik at axb = n, eller ganske enkelt ab = n.
La oss bekrefte dette gjennom et eksempel.
Tabellen nedenfor viser faktorene til tallet 18 som forekommer i par. Du kan bekrefte det samme for noen flere tall hvis du vil.
Vær også oppmerksom på at √18 er omtrent 4,24.
Og i faktorene som forekommer i par (a, b), kan du se at hvis a er mindre enn 4,24, så er b større enn 4,24 – i dette eksemplet, (2, 18) og (3, 6).
Faktorer på 18 i par
Figuren under viser faktorene til 18 plottet på tallinjen.
Hvis tallet n tilfeldigvis er et perfekt kvadrat, vil du ha a = b = √n som en av faktorene.
▶️ Se på faktorene 36 i tabellen nedenfor. Siden 36 er et perfekt kvadrat, er a = b = 6 en av faktorene. For alle andre faktorpar (a, b) gjelder a < 6 og b > 6.
Faktorer på 36 i par
Oppsummert har vi følgende:
- Hvert tall n kan skrives som n = axb
- Hvis n er et perfekt kvadrat, så er a = b = √n.
- Og hvis a < b, da, a < √n og b > √n.
- Ellers, hvis a > b, så a > √n og b < √n.
Så i stedet for å gå gjennom alle heltall opp til n/2, kan du velge å kjøre opp til √n. Og dette er mye mer effektivt enn vår tidligere tilnærming.
Hvordan endre is_prime() til O(√n) algoritme
La oss fortsette med å optimalisere funksjonen for å se etter primtall i 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
La oss nå analysere funksjonsdefinisjonen ovenfor:
- For å beregne kvadratroten av et tall, la oss importere Pythons innebygde matematikkmodul og bruke math.sqrt() funksjonen.
- Siden n kanskje ikke er et perfekt kvadrat, må vi kaste det inn i et heltall. Bruk int(var) for å kaste var inn i en int.
- For å være sikker på at vi faktisk sjekker opp til √n, legger vi til en pluss ettersom range()-funksjonen ekskluderer endepunktet til området som standard.
Kodecellen nedenfor bekrefter at funksjonen vår is_prime() fungerer korrekt.
is_prime(8) # False is_prime(15) # False is_prime(23) # True
I neste avsnitt, la oss lage noen enkle plott for å forstå O(n) og O(√n) visuelt.
Sammenligne O(n) og O(√n) visuelt
▶️ Kjør følgende kodebit i et Jupyter-notebook-miljø etter eget valg.
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)
Utdraget ovenfor viser hvordan du kan plotte kurvene for n og √n for en rekke verdier.
- Vi bruker funksjonen NumPy arange() for å lage en rekke tall.
- Og så samler vi verdiene til n og √n opp til, men ikke inkludert 20, til en pandas DataFrame.
- Deretter plotter vi ved hjelp av seaborns linjeplott() funksjon.
Fra plottet nedenfor ser vi at √n er betydelig mindre enn n.
La oss nå øke området til så høyt som 2000 og gjenta de samme trinnene som ovenfor.
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)
Fra plottet ovenfor kan du slutte at O(√n)-algoritmen er betydelig raskere når du tester om et stort tall er primtall.
Her er et raskt eksempel: 2377 er et primtall – bekreft dette!😀
Mens O(n)-tilnærmingen vil ta størrelsesorden 2000 trinn, kan O(√n)-algoritmen hjelpe med å komme frem til svaret på bare 49 trinn.✅
Konklusjon
⏳ Og det er på tide med en rask oppsummering.
- For å sjekke om et tall er primtall, er den naive tilnærmingen å gå gjennom alle tallene i området (2, n-1). Hvis du ikke finner en faktor som deler n, så er n primtall.
- Siden den eneste faktoren på n større enn n/2 er n selv, kan du velge å kjøre bare opp til n/2.
- Begge de ovennevnte tilnærmingene har en tidskompleksitet på O(n).
- Siden faktorer av et tall forekommer i par, kan du bare kjøre opp til √n. Denne algoritmen er mye raskere enn O(n). Og gevinsten er merkbar når du sjekker om et stort tall er primtall eller ikke.
Jeg håper du forstår hvordan du sjekker om et tall er primtall i Python. Som et neste trinn kan du sjekke opplæringen vår om Python-programmer om strengoperasjoner – der du lærer å sjekke om strenger er palindromer, anagrammer og mer.
Vi sees alle i en annen opplæring. Inntil da, glad koding!👩🏽💻